I've actually been using http://www.stevensonsoftware.com for VPS
hosting. Its very affordable and the support has been great. I got
up and running in minutes. I pay $40 / month for the "Large" plan
(512mb RAM, 20gb storage, 80gb bandwidth). That costs less than the
other services you were asking about.
Hope this helps.