We use Gnax for Hawkee, but that might be overkill for what you're trying to do. A lot of people use Bluehost for basic shared hosting, but I'm not too familiar with other companies.

I've gone through several VPS companies. First you need to determine which is better for you: Xen or OpenVZ. I'm currently with bhost.net and haven't had any issues. I've tried companies like neosurge and had horrible experiences.

Check out VR.org I used them for a few months had a great experience. Very flexible with what OS you can run. From Ubuntu to gentoo.

So far I've heard a lot of good things about DreamHost.com and its support.

I also hear that Site5 is pretty nice.