I've used Linode and Slicehost with great success.
I've also discovered recently Mosso which might be interesting depending on target usage. It's interesting to know it's owned by Rackspace and so is Slicehost. Mosso (now called Rackspace Cloud it seems) offers a really simple interface for creating virtual machines, similar to Amazon's EC2 offer.
All of these let you choose from a range of distro and give you complete root access to configure the server as you want. Support for Linode and Slicehost has been great although my experience has been even better with the latter.
Finally, you can also have a dedicated server at iWeb (amongst others) for pretty cheap where you don't need to take care of the hardware itself. They offer a wide-range of support package too if needed. If you really want to use virtual machines, you could install Xen on a dedicated machine and manage as many VMs as the hardware can handle.