I had a bad experience with GAE, as you are forced to work with their API for many things, some components don’t work as GAE blacklists some package they require, etc. Also, moving from GAE to another platform can be painful.
Amazon can get expensive depending on the resources you use. I don’t know about the others.
The standard option would be Playapps.net, the basic plan is cheap and it provides everything you might need.
Another alternative is to pick a cheap Linode and set it up yourself. It’s a bit more expensive and more work, but better value for the bucks.