One of the most interesting small robots on the market is the PicoBot from 4Tronix (http://4tronix.co.uk/blog/?p=708).
These are small, relatively low-cost robots with a good range of basic sensors based around Arduino. A nice feature is they are quick to put together (5-10 minutes each for the two above). The size, time to build and the radio modules make them an interesting option for playing with swarm robotics - if only I had the money.
Don't let the swarm robot idea put you off, as small robots to playing with programming they are good in their own right. Being small with the ultrasonic sensors gives them an non-threatening look; add in they have some build it programs to play with (select by buttons on the bot) to get you going without any programming.
All opinions in this blog are the Author's and should not in any way be seen as reflecting the views of any organisation the Author has any association with.