What I do use:
1. VPS from a quality hosting company. I use RimuHosting and people I know also like Linode. I like the extra level of managed server support for backup, maintaining RAID devices, etc.
2. AWS - love AWS. Some people have problems with performance of SimpleDB and SQS but these services handle queries in parallel so, for example, for a web app that needs to access a lot of data to render a page, queries can be done all at once. (Same comment on AppEngine's datastore)
3. AppEngine - great if your application is a good fit for the platform. Watch out for long loading request times: I use Java with Objectify, and I can keep loading request times down to about 1 second. (Non-loading requests are obviously a lot faster).
4. Heroku - for Rails apps. Love it.