You can also try painted on anti-slip elastic material for inexpensive tires. O-rings work, too, but they are not flat and hence do not provide as much friction as flat surfaces.
Inner tubes of mountain bike tires also make excellent tires. If you have a ``holey'' tire around waiting to be dumped, cut it up into small sections about the size of the wheel. Compared to rubber bands, the rubber used in inner tires is considerably more durable.
If you insist to buy `professional' tires, I suggest the type used for model airplane landing gears. These are generally thinner so your robot does not become too wide.