Dreamhost is great, but with their basic plans, you aren't root, so your options are limited to Apache/PHP/CGI/MySQL. This is usually good enough for me, but I sometimes have trouble installing and running Perl or Python modules from my home directory.

Elsewhere on this board somebody posted a list of personal colo services; some of the virtual Linux services look attractive, since they offer root privileges at a low cost. Has anybody tried one of them?