This very site, and quite a few others of mine are on
rosehosting - I've got a platinum virtual server, which gives you root access, 4000mb storage and 40gb transfer p/month for about $55 p/month.
The good things are lots of space/bandwidth, and very thorough support (if a little sarcastic sometimes if you do something daft
). The bad things are (depending on your point of view, for me it's a good thing) is that you'll have to learn all about Apache and some Linux fundamentals. If you want to install Java, Tomcat,etc you'll have to do it yourself, but it comes with MySQL/PHP and lots of other goodies pre-installed.