Next time you have a tire off of the rim, measure the inside width in mm, and then look at the chart on http://www.sheldonbrown.com/tire-sizing.html (down at the bottom) to see how wide of a tire would be suitable (plus, check the fork and stay clearances) for your rims. Many of the more durable (and heavier) tires end up being wider.
Tires sold as "city" or "touring" or "randonneur" are often more debris-resistant. Costs will vary substantially from Kenda to Panaracer to those nice Schwalbes. Michelin's "Dynamic" and "City" are not bad, too.