If you're looking at off-road ability, you might also consider wheels. 1293
modified their 2005 robot--based off the kitbot of the day--to accept the pneumatic wheels from the 2004 kit of parts to allow it to run under power in parades. (Well, except when that set screw backed out with in the Irmo Okra Strut Parade--with the bubble blower and extra batteries added, that was probably close to 200 pounds to push.) It wasn't hard to do, and was plenty capable of running on grass, bricks, asphalt, and most anything else that was roughly level.
Of course, treads have their own appeal...but I'd at least consider wheels as an alternative.