Microchip is a great uC to start with. They have an in-circuit programmer that looks like a red and white hockey puck. If you use that you can get surface mount PIC processors as small as 6 pin SOT-6 packages, and you program them while they are attached (soldered) in the circuit
this would really open up options for you - you could start with tiny robots with micro servos, or tiny control boards that you could fit into anything.
Once you build a micro-bot with 2 input and output channels, you will have a better understanding of the overall picture, and will know what you want to do for your next (bigger) project.
http://www.microchip.com/stellent/id...&part=DV164005