You can still look at the iRobot Create (a robot without the vacuum cleaner from the makers of robot vacuum). It's like a simple decision, of course expensive, because it is almost ready.
As for the program filling — not necessary fixed at the Arduino, although it is the easiest microcontroller complex for beginners. Still management you can build on the platform of FEZ ( website TinyCLR.com in ARM-based and .Net Micro Framework), any other ARM platform (the firmware is Linux-based), Chumby (ARM, Linux), BasicStamp2 (microcontroller complex, complicated Arduino, but much smaller, choice for specialization, when it is clear that it needs to do). Well, the top skill — on-net AVR and Atmega without complexes ready =)
By the way, I would like to mention the simplest control method — an asynchronous bitbang mode of the FTDI controller. Require a wired connection to the robot, but the minimum cost for everything you need for 4 lines input / output — an old data cable from Nokia or to any compatible with this controller inside.
