Over the last few years, I've used a few different VPS providers, most notably Bytemark and Gandi -- Bytemark have been excellent, and their support is second to none. Gandi have been reasonable too, although pricey for what you're getting.

A few months back I got a 'Micro' EC2 instance from Amazon, and have been fiddling with it. I took the plunge and got 2 more this week, and have been moving stuff over. The 'Micro' instance is (up to) 2 cores and a reasonable chunk of RAM for running one or two small websites. It's basically a VPS, and the management console lets you take snapshots of your root disk. If you only want a machine to install a random OS on for a few hours and play with something, you can do that, too, and it costs a few cents.

The Micro instance is something like 55 USD a year, and the hourly usage charges bring it up to about 142 USD a year, whcih considering Gandi want 24 EUR and Bytemark 17 GBP per month for the same thing, is not to shabby at all. I've cut my hosting bill and gotten some nice management features on top of it. You can also do loadbalancing between your instances for something like 20 USD a month. Highly recommended so far.