Lego Mindstorms. The great thing about them is that they combine both the mechanical design aspect (why use wheels or tread? what happens if the robot is too big and isn't stable enough? etc.) with the programming side of things.

For something more "pure electronics" oriented, I also highly recommend the book Junkbots, which focuses on building small robots (that do fun things) out of household items:

http://www.amazon.com/JunkBots-Bugbots-Bots-Wheels-Technolog...