Linode and Slicehost will be the two most common answers. They are similar to each other. I am a happy Linode customer.

You say that performance can be low, so you might look here:

http://www.lowendbox.com/