It’s still a bit of a Wild West in terms of VPS providers. There is Amazon’s EC2, Rackspace…. and then there is everybody else. Amazon seems to have a “micro” tier for $2.30/mo…. but you have to pay 3 years in advance for it ($83 or $28/yr). Rackspace, on the other hand will only do managed hosting, which means you’re paying almost 5x the price at $11/mo ($132/yr).
Now if you look at some of the…uh, independent VPS hosts, (most of them are probably resellers) prices typically range from around $5.00-$7.50 ($60-$90/yr). This is a volatile market and I won’t attempt to make any suggestions. Slicehost had a $5/mo deal going if you bought 5 years worth of service, but they were swallowed up whole by rackspace about six months ago, and Linode comes highly recommended by many people, but start around $20/mo ($240/yr). That is not “cheap” tier pricing.
There does seem to be a website that keeps (rough) track of the wild west, they are called lowendbox.com and are able to point out some of the cheaper VPS providers. Sadly most of these places look like fly-by-night operations in comparison to the reasonably priced Amazon EC2 micro tier.
In my case, I need to be able to run a python script 6 times an hour, 18 hours a day. That’s it. Unfortunately my GoDaddy hosting account doesn’t really handle the kind of python functionality I need, and has nerfed quite a bit of the PHP5 functionality as well. So here I am, looking at a proper VPS to run some web apps of mine as a service.