To take it a few steps up from the bristlebot idea, I can seriously recommend this book.
http://www.amazon.com/JunkBots-Bugbots-Bots-Wheels-Technology/dp/0072226013/ref=sr_1_1?ie=UTF8&qid=1293486832&sr=8-1Everything is made from salvaged electronic junk, and they all actually do things. Line followers, racers, walkers, sumo-bots etc.
A bit complex for a 3 year old to get too involved in the construction, but with dad there to do the dirty work the results can be fascinating. My youngest son was about 12 and we had hours of fun working through some of the projects. They are very much "open source" designs and you need to tinker and fine-tune the finished beasties, which just adds to the challenge, and the sense of satisfaction.
As has been said, this stuff gets fearsomely addictive. It's been a while since I made any, but even now I can't throw dead electronic items away without wondering if they have any usable relays, motors or IC's inside.......

one_rod.