I've written the same app on GAE (Python and now Java) and Azure. I'll probably continue to use both, for different things. Here are a few thoughts that I'll keep updating:
Reasons to use GAE:
You don't pay until your app grows quite a bit. With Azure, you pay almost $100 each month, even if you don't have a single website visitor. If your db goes over 1GB, you pay an extra $90 ($9->$99) for storage.
GAE's payment is also very fine-grained - only for the resources you use. Azure (and AWS) is "blocky" - you pay something for each server instance you'll run (plus resources), irrespective of whether it gets any use at all.
GAE has the lightest admin load. Once you're setup, deploying and re-deploying is quick and they'll auto-everything. For example, you don't worry about how many servers your app is using, how to shard the data, how to load-balance.
Mail just works. At the time of writing, Azure doesn't offer SMTP out so you need a 3rd party server.
Great integration with many of the Google offerings - calendars, mail, whatever. You can delegate user management to Google if you don't want control over your user base.
With GAE you know any features they add to the store, you'll get. With Azure, you get the feeling Sql Azure Database will get most of the love but it'll be more expensive. Azure Storage is likely to have the most gotchas. No relational integrity, no order-by, you'll fiddle with the in-memory context more. GAE's store has far fewer restrictions and more features than Azure Tables.
Good choice if you're using Python or JVM-based languages already. Many languages compile to Java bytecode nowadays.
Updating the app is very fast. For Python, I had a shortcut key setup and it took no time at all. I now use the Eclipse Plugin for Java and it works very well. Azure is more fiddly.
A locally tested app will probably run on the cloud without (much or any) changes. With Azure, the config is different and I spent some time stopping-deleting-building-uploading-starting before I got it right.
GAE has a great UI that includes a log viewer a data editor. With Azure, you currently have to find external viewers/editors for this.
GAE lets you have multiple versions of your application running on the same datastore. You can deploy, test a version and then set the current 'live' version when you're ready. You can change back if something goes wrong.
Reasons to use Azure:
I've read of users getting "I think you're a robot" messages, like sometimes pop up on other Google properties. I haven't seen it, but it would alarm me.
Azure seems to be better designed if you have a SOA-type approach. Their architectures seem to benefit from experience in the enterprise world. GAE seems more focused on simply serving web pages.
You can run the app under debug, put in breakpoints, etc.
Azure has a "staging" environment where you can deploy to the cloud, but not make it live until you're happy it works.
I'm using .Net for other things, and integrating them with .Net on the backend is much easier than with GAE. (Update - using Java on GAE works fine, and the 10-second timeout is now 30 seconds).
Azure has two approaches to storage, offering more choice. They are SQL Azure Database (SAD) which is a relational DB, and Azure Storage, which consists of non-relational tables, blobs and queues. If you have an investment in SQL Server then SAD will be easy to move to, but is quite costly and *might* be less scalable.
Integration with many MS "Live" offerings.
So, no obvious answers. I'm defaulting to App Engine at the moment because of costs and ease of use. I might use Azure for very MS-oriented apps. I use Amazon S3 for downloads but likely won't use EC2 because I prefer leaving everything under the application level to the experts.
