I've been on AWS for almost a year now. We haven't yet needed the real benefits, which is the potentially easy scaling.

If you're starting out and don't see yourself getting INSANE load requests in your first several months then I would go with slicehost, as it is much simpler to get started with.