My Galaxy was supplied with 700x32, and I stayed with those for years. Before my trip to Oz, I asked in the LBS and took up their advice for 28's, which are considerably smaller then the 32's. They are M+ Schwalbes, the ones with the anti-fairy band round the running surface, and come up a little bigger than other 28's. 1000 miles without problem in Oz, including a lot of unmade roads. Less comfortable, but quicker, than the 32's. I wouldn't like to go any amaller on those rims, but did run a 36 for a while on the rear when my tyre failed big style in Spain, and that was the smallest I could buy.