Efficiency.
Read up on the AO Smith water heaters they stock. You want one with a rapid recovery time (how fast it heats water) and of course how efficient it is. If you get one that is of high enough efficiency, you will qualify for a 30% tax credit. Also, see if the new water heater uses electricity for gas ignition or for a blower. The more efficient ones do, but if you loose power, you loose your hot water. On our older gas water heater, there is a standing pilot which is unaffected by power failures, but is less efficient.
We saved $20.00 per month on our water heater's gas bill (our water heater is the only thing on the basement gas meter). We did this by insulating all the hot water pipes we could get to. We insulated the pipes in the basement, the ceiling of the 1st floor (it collapsed when I reconnected the plumbing for the 2nd and 3rd floors due to ice cracks, it was not fun), the wall of the 2nd floor, and the ceiling of the 3rd floor. Copper is an excellent heat conductor and insulating the pipes made the water noticeably hotter at the tap and saved us $20.00 a month on gas. I can't complain.
Pipe insulation is about $1.00 per 6 feet. We used the pre-slit polystyrene type with no adhesive. Just cut to length with scissors and slip it on the pipe. It reduces noise too. It's fast easy, and cheap!
Also, make sure they use 3/4 inch pipe. 1/2 inch is cheaper, but is restrictive and reduces flow if it's used for a main line. 1/2 inch is suitable for branch service (like supplying individual faucets and fixtures, but not more than 1 thing at a time). Even if your house is plumbed wrong with 1/2, use 3/4 and it's that much less that you'll have to replace later.
Good luck,
Dave