+4  A: 

Well, some good VPS solutions that allows for pain free upgrades and are really cheap are Linode and Slicehost. The problem here though is they aren't setup and forget..if they need an upgrade, you have to manually do it. However, with those 2 hosts, you order the upgrade and it is performed painlessly in less than 5 minutes. All your files will be intact.

Based on your description, though, it sounds like you want a cloud host where you can just set up the server and have it automatically scale to what you need. In that case, you'll want to check out Amazon EC2 and Amazon S3.

ryeguy
+1 more for Slicehost coming from a very satisfied customer ;-) Slicehost is really meant for people who want to get involved in the "dirty work" of maintaining a server, i.e. upgrades and such. If you want to set it and forget it, VPS isn't really the way to go.
David Zaslavsky
The benchmarks I've seen show Linode being faster, and it comes with more memory, disk space and bandwidth. EC2 is more scalable (more scalable than 99% of people will ever need), but it's also more expensive and the latency is higher.
Brendan Long
A: 

I've used RimuHosting, they have great service (respond in minutes a lot of the time). They'll see you up with a Virtual Server however you want and you get root access and get configure it how you'd like. If you need help with something, they've always helped me very quickly. You can pick between whichever distro or software you'd like.

Greg
+2  A: 

I've been extremely pleased with webfaction http://webfaction.com. They have stock installations of several popular applications and frameworks (PHP, Django, Drupal, etc.) However, you're not locked into these. While they don't give you root access, they do give you access to a complete toolchain allowing you to compile and install whatever version of whatever components you need.

I've compiled and installed Erlang, ejabberd, couchdb, rabbitmq, activemq, openfire on my server with only minor hitches mostly due to ignorance on my part, not their system.

Joe Holloway
A: 

I've been using site5 http://www.site5.com/ for a number of years now and would definitely recommend them. They support PHP, Ruby on Rails and Python and allow SSH access so you can get quite a bit done. Their support is awesome and they often let you install arb software (they let me have mercurial before it was standard on their setup).

Alistair