My company used GoGrid prior to me getting here. The anecdotal reviews were very very bad. That being said I've never used them and it was 18 months + ago so maybe they are better now.
We use EC2 almost exclusively but do run some instances on Terremark (http://www.terremark.com/services/cloudcomputing.aspx) just because we had some issues a while back where EC2 wasn't letting us create new instances for like a week and we wanted to have some insurance.
EngineYard - http://engineyard.com. they're built on top of EC2 and a little pricey but their support/service is incredible and they make it a breeze to deploy...
http://www.stormondemand.com/cloud-hosting/