I have a VPS from WiredTree (wiredtree.com) and I can't recommend them highly enough. Good guys, great support. The only negative is that the intro VPS (with only 256MB of RAM) is a little weak, and can choke on cPanel. If you're looking for a fully-managed VPS, go with WiredTree.

For smaller-scale sites, Media Layer (medialayer.com) gets nothing but rave reviews on the webostingtalk.com forums, though I don't have any first-hand experience with them. I've used EngineHosting (enginehosting.com) for a couple ExpressionEngine based sites for clients, and they're great, too.