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.