Looking for a new host with VPS

[Retrocheats]

I know there are several members here that host their own sites and have their own personal stories (or nightmares, as the case may be). Post any good possibilities you think we should look at for a new host, or even hosts you feel we should definitely stay away from. "War stories" related to your suggestions would be a nice touch

The only thing I know we are looking for is a VPS host. It will reduce the amount of people we will be sharing a physical machine with. A dedicated server would be even better, but we simply cannot attempt such an expensive endeavor at this time.

So can you guys help us out?
It would be even more helpful if you have personal experience with the host.