Thanks guys!
The wheels called "balloon" or "beach tires" and people often use them on off-road beach wheelchair or carts. They are inflated to a pressure of only 2.5psi, so the robot handles the defenses really smoothly. They came with bushings which we broached to 1/2" hex.
We are using the24cm versions:
http://wheeleez.com/beach-wheels-polyurethane.php