I find that for a starter you are quick to dismiss the BASIC Stamp because it uses a variant of BASIC developed by Parallax known as PBASIC.
Having used both the BASIC Stamp and the Arduino, I still have my BASIC Stamp kit, along with the Stampworks book that is freely available from Parallax's website. I don't own my Arduino anymore having sold it to another student who ALSO felt that he wanted to write in C and not in BASIC.
The BASIC stamp is a milspec chip, and has been used on hundreds of amateur projects, and also in household appliances.
For example, the BASIC Stamp has been incorporated within a device that schedules the times a sprinkler system is to be turned on, it has also been used on various different Near Space balloons (very much like the near space project I worked on nearspace.0x58.com for more info).
Dismissing this versatile and useful chip because it does not have a C compiler is a mistake. It will be easier to prototype with, easier to quickly build various projects, and does not require the extensive knowledge of writing C code to run on an embedded platform.
Once you are done with the BASIC Stamp, you can move up to Parallax's SX28. This is a chip that can be programmed in SX/B (The SX version of BASIC, using those same skills and almost the same code you learned for the BASIC Stamp). C compilers do exist for the SX, as well as allowing you to program it entirely in assembly (good platform to learn assembly on).
Then the next step up is another Parallax device called the Propeller. This gives you 8 different cores to run code on, all in an embedded device allowing you to multi-task. It has to be written in an entirely new programming language called Spin, but by the time that you have taught yourself BASIC and SX/B you will have come to understand Parallax's awesome resources, awesome manuals and guides, and Spin will be nothing.
I have worked with Parallax's products for a long time, Just recently have I started moving to the Ti MSP430 for a new project I am working on, mainly for a new challenge as well as it having everything I needed on a single chip.
My outright suggestion, if you had not guessed it yet, go with the Parallax BASIC stamp. The ease with which you can the things you want to do, especially as a beginner make it a great starter set.