looking at the challenges up above i believe i have found a form of locomotion that would satisfy all of them.
a robot that uses Augers to contact the ground.
http://www.youtube.com/watch?v=1uynmApjhWI
better yet, a robot of this type would be somewhat holonomic if the augers were separately driven, it would also have incredible amounts of traction, even more than tank treads i believe. it could go up stairs if the auger diameter were large enough, and if the Augers were hollow or could float, it might contribute to a water game. i suspect that depending on the pitch of the augers, not much gear reduction would be needed for a working robot, a single AM stack-box would probably do the trick.