It should be noted that many of the services that have been mentioned (heroku, dotcloud) are built on top of AWS, so they'll be no more reliable than AWS.

Other big players in the cloud space are MS Azure and Rackspace.