I can personally recommend the Boe-bot. Depending on your programming and electrical experience the you may be able to breeze right through the tutorials but for a beginner they are a great guide and teach a lot of the basics. This is how i got started in robotics!
If you have some experience it is still a great little platform and is easy to add sensors or other mechanical bits, with an onboard breadboard and slotted aluminum chassis. I recently revived my (10 year old) boe-bot outfitting it with a new arduino. I had the little robot following my foot or wandering the apartment in no time. At one point I was working on turning the boe-bot into a vacuum, never completed the project but did get a good part of the mechanics and some of the electronics built.
Also note, the robot is available in several versions including arduino or basic stamp controller.