Linux virtual hosting is all the rage today and there are literally thousands of companies doing it. One of the old hands in this market is Linode.com. They offer the usual type of thing really, bunch of operating systems to choose from, remote shell to manage it and the VM is essentially yours to do as you please.
Where they really shine though is in their admin tool, it allows you to profile your machine and allocate your alloted storage in many ways, you could for example have 1 linode with 20GB drive space but only use 5GB for one machine running Debian. The rest of the space can be used with OS images for RedHat or something else and you can freely choose to boot any of these as long as you only have one going at a time. I've not tried but you could no doubt also share 1 swap partition amongst a lot of OS images, or one /home partition so your development environment travels with you between the various operating systems.
That is really great for software developers who need to test their apps on many distributions. I've had machines at them since around 2003 now and have not once had cause to open a support ticket with them. I obviously had outages, the host machines need upgrading some times too and they post work notices on their forums etc about this.
The big thing though is that they don't just leave you stuck with what you had years ago, they constantly upgrade you as they get more capacity. My machine there started off with 128MB RAM and 3GB drive space it has since without any involvement by me transformed into a 300MB RAM and 10GB storage allocation machine. Obviously my OS image did not grow, I just have some spare storage to allocate to VMs now. Really helpful when I want to rebuild the machine for instance to a newer version of the OS. My bills for these upgrades? Zero, no increase in rate and no setup charges.
If you're in the VM market and looking for a machine in America, you just have to look at Linode.
I vouch for linode too - on your advice a few years ago I've been using them pretty much since then. I've noticed, of late, that they're having more network issues than ever before - but @ the price and the generally working flawlessly I'm okay with a few network issues :)
Don't forget, you can resize your existing disk image to take advantage of the new space if you wish. It's just a shutdown and then a disk resize via the website and then you are back up and running with more space available.