The three things that I ask people to consider when they're replacing a roof is if they're in a wind or hail damage region, and if they're in a region with high solar gain (such as Texas) or an area prone to ice damming (such as New England or the upper midwest.)
If you're in an area that is prone to wind or hail damage (thunderstorms or hurricanes), you might want to look into a more resilient form of roofing material. Stone-coated steel shingles (which look just like standard asphalt shingles) are a great product that will resist most forms of damage that can be dished out. Your insurance may give you a discount on them because they have a longer lifetime.
If you're in a high solar gain area, look into some of the energy-star rated shingles. They again look just like stone coated asphalt shingles, but they'll help keep your attic cool in the summertime.
If you're in an area that gets a decent amount of snow, make sure that they install an ice & water barrier around any roof penetrations (like skylights or places where they replace a vent) and along the edge of the roof where you could develop ice damming problems. This material is a sticky membrane that self-sticks to the roof deck and basically keeps water from seeping through at all. Common brand name for this product are "Grace Ice & Water Shield" ... I also personally use it in roof valleys, gable crotches, and several other places where water tends to get blown up inside something and you really don't want it to soak through.
You definitely want to get your insulation up to the max, but that's something that you can do at any time using blown-in insulation. If you are replacing roof decking and have it open, you should make sure that you have plenty of soffit vents and that your soffit vents are baffled properly. (I like the Berger Accuvent, personally...)
You want to make sure that any damaged or rusted flashing is replaced, and that tar paper is replaced. Look into what kind of tar paper they're using (heavier the weight, the better...), because that's actually your roof. Make sure you know what kind of valleys you're getting. For standard asphalt shingles, I prefer woven valleys, but they're harder to do and therefore are more expensive.