We used Amazon and got bad performance in the beginning too. It is bad when you pull files out of S3. By bad I mean the latency is high.

We tried GoGrid and they lost or crashed our server instance.

I've personally used Rackspace, so far so good, but I've only been doing development on it.