Here's my take on it.
Buy a low mileage Cavalier, a new 5-spd (like somebody else mentioned), etc... They are cheap but very frugal on gas, no special fluids, easy to repair and generally durable if not quiet and tightly built.
You could also get a Civic - 2 co-workers have them and one gets 39.5 very consistently (and it's winter right now) and they are about as durable as you get. You could also get the 4-banger Accord. I have a 2002 Accord V6 (3.0L) and I get 20-22 mpg in the winter with 50/50 city/highway and Blizzak's, and it will get 29-31 on the highway (with the air ON).
My old Buick Roadmaster got 17-18 around town and low 20's (up to 24) on the road, and that's with a smallblock 350 and turbo 700 with lockup. That car has 287,000 miles on it now.
Personally, I'd look for a used low mileage Civic or Cavalier for mileage concerns. No such thing as a truck that gets "great" mileage. My father's 2000 Suburban (6.0L, 2500 HD) can get into the low 20's easily, and usually runs 18+ mpg. His former 1994 Ford F350 with the 460 got between 18 and 24 easily, if you kept your foot out of it.
A family friends 1992 Accord gets 24+. All of these vehicles have been as reliable as a stone axe.