Attributes: cheap, simple, indestructable (so I can spend time writing software rather than fixing hardware).
Maybe a very simple piezo actuator that can both hop around and do some at least minimal sensing? Strap a supercapacitor or tiny dense battery on, and an SMT microcontroller, and it's a very cheap mostly indestructable robot?
Freaky suggestions of low-power AM stuff (simple circuit here and here) (analysis here)
Apparenlty supercapacitors aren't very energy-dense compared to batteries. Among batteries, NiMH are the most dense. According to digikey, a 650mAh 12gram AAA battery can be had for $3. (though it needs the super-fancy charger that Winsor has)