Note: most of the restrictions for AppEngine should be resolved with Managed VMs launching soon.
As you might know I'm currently working on my top-secret project, called JOPPFM. It requires some heavy work on the server-side, so choosing the best PaaS / SaaS is critical. At first, I planned to use AppEngine. Unfortunately AppEngine restricts you to use HTTP only, but I need IMAP / POP and XMPP too.
A few weeks ago Heroku introduced support for Java, and I've decided to ditch AppEngine in favor of Heroku, because the easy deployment (using git) and the freedom (use whatever protocols you want, unlimited bandwidth, unlimited database read and writes, etc) fascinated me. So I started developing JOPPFM for Heroku and yesterday I finally managed to get a first prototype up and running.
During development I faced lots of problems and shortcomings of Heroku and decided to migrate to AppEngine after finishing the first prototype. So, here I am. I think I'm now able to compare those two services for you...
Take a look at AppEngine's extensive documentation here. Almost every feature AppEngine offers is described here. Note that this documentation is language-specific! No general blabla, but actual code in the language you're working with.
Heroku offers an extensive documentation too... but not for Java. Almost all official wiki entries are for Ruby. The Java-specific documentation you can find on heroku.com is their announcement of Java support on their blog, which describes the first steps of getting an app up there. Fortunately one of their employees, James Ward, seems to be a Java developer himself and wrote a great "workbook": "Heroku for Java Workbook".
Still, that's not comparable to what Google offers. Goal for AppEngine.
TL;DR: Heroku wins this point. You're allowed to do almost everything! Run threads from servlets, connect to an IMAP server, etc. The only "restriction" I remember at the moment is a timeout at ~60 or 90 seconds on HTTP connections. However, this only counts for idle HTTP connections. Push some data out there every 30 seconds and you're good to go...
So, if you already have a Java server running, you could run it without any modifications on Heroku.
AppEngine is restricted by design. I guess it's for the sake of security and performance. That's a good reason to restrict developers, but I would still love to workaround this somehow...
For this purpose, Heroku offers... erm... nothing? Ok, I have to admit: if I didn't mix up SaaS (which Heroku is) and PaaS, SaaS doesn't offer administration tools by design. That's what it's supposed to do: run your app. Additionally, you have access to your app's output, but that's it.
PaaS however, which AppEngine is, offers you great tools for logging events and errors, measuring your load and performance and so on. AppEngine does that job pretty well. Heroku 1 : AppEngine 2.
Both, AppEngine and Heroku offer you some free stuff. Every month, again and again! Basically they offer the same: one instance is free. Additionally, you get unlimited bandwidth and a 5MB (!) database.
The free tier at AppEngine is... different. Take a look at it yourself here.
It depends on your needs which service wins this category.
I'm not sure if I prefer direct access to a (Postgre-) SQL database, or if I prefer a wrapper, like the excellent objectify-appengine. Again, decide yourself...
That's it. I hope you keep these facts in mind for your next app.