First of all, this is probably a personal question but, do you have good credit?
Cause if so, you might as well go with a new car.
Sedans now a days, from really good makers, are actually pretty cheap brand new and save you a TON of gas.
I did A LOT of research before I decided to buy my Mazda3 4 door and I absolutely LOVE IT!
It gets 32 miles, I believe, to the galon and I got mine brand new, since I have good credit.
When I was car shopping I was thinking about getting a used car as well...but then I figured that with a used car, I could probably spend a bundle on repairs if the previous owner did not take good care of it, so I didn't take any chances.
The popular sedans are of course the Toyota Corollas/Camry and the Honda Civic/Accord. Pretty good gas mileage on both, big and cozy, and are pretty flashy on their own.
Now if you're looking for something a lil bit more "masculine" but still gives you more miles to the galon, then I PERSONALLY suggest the Mazda6.
Kia and Saturn make really good sedan cars as well that have pretty good mileage.
So my advice is to definitely do your research, compare cars from each maker and visit your closest car dealer and take it for a spin and see if it's the right car for YOU.
I personally wouldn't suggest on investing on a used car...but 'ey, I know times are tough right now so get what you can get. Just be sure to ask for that CarFax report and get it on the early 2000's.