In my experience Dotcloud has the advantage of giving you more control over your instances and the ability to SSH into them. But I had issues with the reliability of deployment there. I used to love the sandbox, but I dropped Dotcloud as a provider after that was removed without a drop-in replacement. However, I still use them to serve Redis, and so far, it's way cheaper than using a dedicated Redis service.

I looked into AppFog, but it was not nearly customizable for my fairly intense Django app. I found too much of the configuration to be baked in.

On Heroku, I really like the ease of connecting third party services, and the fact that many of those services have free tiers. I love their New Relic pricing as well. I like that Foreman/Honcho make for a pretty awesome staging environment. What I don't like is the inability to directly connect to dynos.

So far, of the products I've tried, Heroku seems the closest to being fully baked, but it's still a ways away from hitting it out of the park. I'm really glad this question was brought up, even if it's quite frequently asked. There are so many players and the scene is so rapidly changing that information is constantly going out of date. It seems to me that what's really needed is some sort of ongoing comparison tool/site to track the whole PaaS scene.