I had a '91 Honda Accord station wagon that I loved. It was still running great around 275,000 miles, and the station wagon gives you tons of cargo space. A friend and I even camped in it by dropping the back seats. I currently have a Civic hybrid, but the mileage improvement isn't actually that great compared to the premium you'll pay. I got a great deal on mine from a friend that was leaving the country. Toyota Camry I seem to recall has the best longevity of any car out there, but they're priced fairly high even with a lot of miles on them. On the downside, neither of my Hondas have been great in the snow. My parent's Subaru Forester was fantastic even on slick roads, and also has excellent storage and seating.
If you drive stick, you'll get a lower price and better mileage. You can also look for those cars that scare people. I had a Dodge Neon, in great mechanical condition, bought off Ebay for $1000. That same vehicle would have been $3000, but the speedometer and gas gauge didn't work. I drove conservatively, using my gear and the engine sound to guesstimate speed, and tanked up frequently. I had no major issues with that car for the 2 years I owned it (and never ran out of gas), and I sold it for about $250.