Seconded. Dreamhost seem to get quite a bit of flak due to their size, but I have an account with them for "secondary" stuff and it works excellently for that. I'd only use my own dedicated servers for the proper stuff though :)
For virtual dedicated, I use Slicehost (http://www.slicehost.com) to host The Photo Stream (http://www.thephotostream.com) and they have been excellent for the past two months.
I've been using Dreamhost for a while now (to host my blog) and it has been pretty much okay but I wouldn't host any critical stuff on it.
WebFaction (http://www.webfaction.com) and Slicehost (http://www.slicehost.com) are pretty popular lately (although not _that_ cheap). I would probably go with webfaction for a django app.