It would be helpful to know something about your requirements: as you move away from commodity hosting, the hosting world becomes more complex in what it provides.

I've been very satisfied with my Slicehost (http://www.slicehost.com/) account, for excellent virtualized hardware, but depending on your scale, need for growth, geographic location, need for dedicated boxes, et cetera, someone else is likely appropriate.