I had a more, um, limited budget of $5k for my car. I ended up with a really mint '97 Civic HX from the original owner. The car has never had a single problem for me and gets 42-50 MPG depending on conditions. You may want something newer, fancier, sophisticated, but there are nice efficient cars out there for far less than $20k.
If I had your budget, however, I'd buy a used Honda Insight and use the left over cash to install a MIMA other mods. But again, that's not for everyone.
Additionally, the Honda Fit is a wonderful little car, and probably the best value in the small car market right now. I would hold on a year or two though, as Honda has hinted of sending the US a diesel Fit for 2009, and that will give the same great little car with 50+/- MPG. That, or wait for the upcoming Honda CR-Z concept to materialize... mmm...hybrid sports coupe...