Note: I am looking at the cheapest solution at the moment but I would pay a bit more for quality.
When I asked around my friends, http://www.wizzvps.com/ was recommended if I didn't need the 'support' of Linode.
I had a severe crash at Linode years ago causing a complete loss of data. They did work with me for days trying to recover the filesystem and I found their support staff knowledgeable and helpful.
I never had problems with SliceHost so I don't know much about their support.
I'm using AWS because a reserved micro instance is super cheap at just under $10 and because I manage a much larger AWS infrastructure at work so it's nice to work with the same APIs for my own stuff and work. I also think the skillset is more transferable if you're learning.
I have also spent a couple of years with Slicehost, who have excellent docs and a reliable service. It's fair to say that I learned most of what I know about syadmin stuff while hosted with Slicehost.
When Slicehost got bought out, I switched to their new parent RackSpace to get some experience with "cloud" stuff. It's working out very well so far. They're a bit cheaper than Slicehost.
It's been rock solid, they have a simple (yet great) administrative interface, and the two times I needed their support, I had a response within minutes (even at 2AM in the morning). Plus they contribute some great docs to budding sys admins and devs, and make it easy to pick up some sys admin basics. Very happy with them.
I switched to Linode and have been very happy. Pricing is good, and bandwidth overage fees won't kill you.
OpenVZ and Virtuozzo are more like chroot on steroids. Those technologies make it easier to oversell hardware and you'll often end up with some pretty crappy performance.
Dislaimer: as of last month, I'm also employed by them.
