I have used RimuHosting, VPS.net, Slicehost and EC2.

Slicehost and RimuHosting by far have the best customer-service experience. I really liked the idea of slicehost, but unfortunately in practice trying to scale up a 4GB instance to an 8GB instance to handle load isn't fast-enough to actually be a great production strategy -- your VM contents are effectively copied to another machine and booted in it's place, so if you have a ton of small files, that copy operation will take a long time, especially if the server is getting hammered.

Also, you cannot scale beyond the 15.5GB instance because it is 1 physical server. So if you have potential massive growth down the road, you'll have to look into load-balancing.

As for cost, I disagree with the few that said Slicehost was expensive -- in our experience it was a lot cheaper than EC2 -- go ahead and price out comparable VM's on EC2 and don't forget the bandwidth, that is where they get you.

Unfortunately we didn't stay with Slicehost because of 2 VM host failures in 2 months. About 3-4hours of complete outages both times and 1 time our VM failed for no reason... it was really frustrating to have all these mysterious issues and it seemed there was no "fix" for these things... they were just god's will or something, who knows.

We moved to VPS.net next and it was great, for 12hrs... in the following week we had 2 mysterious complete failures of our VPS (tried, 4, 8 and 12-node configurations IIRC) and each time the 1st tier support would respond with "Our server admins are looking into it and will get back to your shortly", and then another 3 hours of down time before a useless "Ok, your VM has been restarted" response... that's it... no identification as to why the failure occurred so often or what was going on.

Again, another great idea "in theory" that just ended up sucking for us. However, if you need massive scalability, VPS.net will let you scale your individual VMs up to like 64 "nodes" -- which comes out to some insanely large machine.

To their credit, I got tweets and emails from the CEO and head of CS to help me after I blogged about the experience... but it is one of those "thanks but no thanks" situations...I didn't want to keep doing that dance with failing servers.

I eventually ended up BACK on RimuHosting -- 2 years prior we had left to try and find a more easily scalable VPS platform after no downtime on Rimu. We got dazzled by these other AJAX-enabled management sites and so on... Rimu has a very simple/ugly web interface, but an incredibly responsive team of very very smart people all dedicated to server stuff... and in the end we just couldn't come close to replacing that with real world experience on high-load sites (Dugg, slashdotted, etc.)

That being said, there are a lot of options Rimu doesn't advertise on their site well that make it one of the cheapest hosting solutions out there... like going over 2TB of bandwidth a month in their Dallas center only costs $0.10/GB -- Amazon is $0.15/GB

They can also scale you up to an 8-core, 72GB monster dedicated server on the high end for $1k/month -- price that same thing out on EC2 with the same allocated bandwidth and it's like $1700 even with the reserved instances.

Then you throw the really responsive customer support that is willing to do almost anything reasonable for you for free (including configing/installing software, etc.) and even though they have no sexy AJAX on their site, my life is a lot easier hosting with them.

We do all our serving through them, even stuff we have to scale over time with growing VPS accounts -- if you need custom setups that aren't on their site, just ask. They'll likely toss it together for you.

--- Hope that helps, I know you have a lot of feedback to read.