Storm On Demand has a pretty cool offering with decent prices. They even have a "bare metal cloud".

http://www.stormondemand.com/cloud-hosting/