I second Win's recommendation. IMHO, the Boe Bot is the way to go! I have
two of them little guys, sweet. As Win said, you get a free scribbler robot
with it's purchase (serial port only with the offer).
Lots of fun and learning...
While you got some really good replys, You might check out the Lego
Some may think it is to much of a toy but there is a lot of online
support and information about the kit (Mostly from hobbists).
While I think it is a bit costly for what the programable brick is, it
still has a lot to offer.
For $226.00 you can get a kit and good starter graphical programing
Then there are other free programming environments like NQC (Not Quite
C, a C like programming language), Lejos (Java based), etc.
Other resources for Mindstorms:
Add on hardware for Mindstorms (Mind sensors);
Polytechforum.com is a website by engineers for engineers. It is not affiliated with any of manufacturers or vendors discussed here.
All logos and trade names are the property of their respective owners.