[Ryan_Todd]

Having personally seen how all of the above wheels (and tapes) fare on all of the aforementioned surfaces, here's a few tips:

1. Don't even think about using any kind of tape as a grip material. You'll either regret it when the tape peels loose and jams your drive mechanism, or when the tape wears away and leaves a nasty sticky coating all over everything. Either way, it never ends well.
2. Everything will eventually wear out if you run it on concrete, with the sole exception of pneumatic tires: those are basically invincible over the kinds of distances that a demo bot can travel in its lifetime. On the other hand, they do cost more upfront, they make long-orientation drivetrains hard to steer, and they require wider-than-normal wheel wells to fit.
3. All of the various replaceable-tread wheels (Plaction, IFI, etc.) are well-known to quickly wear flat outside of a competition environment. If you're ok with bald treads, however, they are suitable for all surfaces: once the treads wear away, their rubber backing is pretty durable, has decent traction, and is non-marking. Taking this path will cost more money than it's worth, however, and the treads do start to look ugly once you've gotten to that point, so you're better off avoiding this category.
4. Slick wheels (the hard white plastic kind that was introduced for the 2009 season) are plenty durable for outdoor use, but they get mangled in the process. They won't "mark" the hardwood floor of a gymnasium, per say, but they will scratch up the floor like a rabid wolverine, so those are off-limits as well.
5. All told, Colsons and AndyMark rubber-tread wheels (or any other hard solid-rubber wheels, for that matter) are probably your best options for this purpose. They will deliver uniform performance across all of the above surfaces, they'll last many years without complaining, and they won't mark or scratch floors when you take them back indoors.