The Parallels Virtuozzo / OpenVZ container-based approach to virtualization is just so infinitely more efficient than hypervisor-based virtualization. It's really, really staggering. We use it where I work for internal virtualization and have done tests with thousands of containers on a box that could hold at most 20-30 KVM-based hypervisor instances.
If you look into the deep tech details, it becomes immediately obvious why this is the case. It's too bad this isn't in the mainline Linux kernel. There is an effort called LXC, but it is behind OpenVZ/Virtuozzo, especially in the security department.
The only disadvantage is that you can't run your own kernel, but for 99.9% of Linux applications this does not matter. You can do quite a bit inside a container: OpenVPN, IPSec, Fuse, IPTables, bridging, etc.
For personal hosting, I've had very good luck with this one: http://alienvps.com/
I have their "abduction" plan -- a very very cheap one not advertised on the homepage. It's very small, but I've managed to cram a stripped-down MySQL and Lighttpd LAMP stack in there for my personal sites. You can't beat the price, and so far I've had no downtime or issues.
This is also the reason why performance is usually beyond terrible. Most of the cheap VPS hosts are extremely overprovisioned and not very well maintained. There may be the odd gem (I haven't tried alien), but $130 buys you a rackspace VM for a year nowadays, so I don't see the point of even bothering anymore.
You don't have to oversell like that. It doesn't change the fundamental, unavoidable fact that containers are a far more efficient way to virtualize than hypervisors for fundamental architectural reasons. An OpenVZ-based hoster that didn't oversell ridiculously would be cheaper and faster than a hypervisor-based host.
With a hypervisor you are running an entire kernel within a simulated machine within another kernel. That will never be more efficient.