Get the narrowest and highest pressure tire you can find. Specialized makes a bunch that fit the bill. http://www.specialized.com/bc/SBCEqS...EquipTires26_1
You might notice one is $ 18 a tire. They are good tires. My GF has them on her bik. No flats yet and she has at least a few hundred miles on them.