+1 for Tirerack.com and I have also heard great things about the Conti DWS.
Surprised no one here has mentioned tire pressure for fuel economy. A low pressure will reduce your fuel economy so always make sure your tires are properly inflated. Properly inflated, mind you, means somewhere within the range of the tire; too low and you'll wear the outsides of the tire; too high and you'll wear the center. Proper inflation is essential for both fuel economy and tire wear.
Also note that different tires, are going to ride and sound different. As a tire snob in a high performance car, I typically by high end, low-profile, stiff sidewalled summer tires. They're noisy and a hard ride but grip like anything. Ultimately, grip is the #1 concern for me. Though I do occasionally worry about longevity.
edit: formatting