The GitHub example is the reason why I never wrote any code against GAE. The lock-in into their data store is a hard pill to swallow and was an early warning sign.
I am not familiar with the internals of Heroku and don't know how they solve the problems I outlined. Maybe someone else can elaborate.
Heroku runs a process for each application (or multiple). The first one for an application is free. But just like with GAE, they'll spin it down if it's idle long enough. So I know that if I go to a site of mine that no one has visited in months, where I'm not paying for extra instances, it'll take a few seconds to load. But having to run those free instances doesn't kill them because all but the first one for an application is paid for at 5 cents/hour, which presumable is enough margin to cover the free instances, and then some.
But they run normal applications. It started out being any Rack (Ruby web standard--Rails, Sinatra, etc) app; they've expanded into other languages now, but it's always some open framework that they're running for you, not something they own and keep proprietary. They give you a normal Postgres database. There are a few restrictions that you might not have on your own hosting (like a read-only filesystem). But you could basically take an app running on Heroku, install a webserver and Rails, install Postgres, make sure any config you had was the same, and run it.
Another huge advantage Heroku has is the ability to give other people access to their datacenters, since they're just running on EC2. So there's lots of Addon services that can add various pieces of functionality, like hosting a different database, many of which are only tractable because they're also hosted on EC2 and thus have very good latency to Heroku servers.
This means that you're not stuck with Postgres. If you think a part of your data, or all of your data, would be better stored in Mongo or Couch or Redis or flat files on S3, there are hosted services for that, and you can even deploy your own solution on EC2 if you'd rather. This leads to nice halfway solutions where you use Heroku to have super-scalable application servers, and maybe to manage your main relational db, but then you can tack on other things where that doesn't fit with your problem. Now, if you're running some of your own EC2 instances, you're losing some of the "never have to worry about hosting again" value of Heroku, but at least it's possible. It could be a temporary solution that keeps you above water while you migrate off of Heroku, or maybe you decide it really is the best long-term solution.
It's interesting, since GAE charges $0.08/hour per front end instance, with 28 front end hour instances free per day. However, I once helped someone debug an application that on average gets one hit a minute, and yet manages to max the 28 free hours and then some. Closer examination showed that GAE was having these instances hang around for much longer than seemed necessary after they fulfilled the initial request.
So either Heroku has more magical magic than GAE, or there is some other kind of efficiency that they are tapping into. One thing I can think of is that possibly Heroku is more conservative with spinning up extra processes, preferring longer response times.
I may be misunderstanding what you mean but heroku does not spin up or down any processes, the amount of workers you have is controlled entirely by the end user and you will be billed by the worker regardless of how much traffic you're getting. I'd venture that 95% of heroku apps have a single process, and that 95% of the time those workers are in some sort of suspended state.
If you have 1 dyno, heroku spins that dyno down after 20-30 minutes of inactivity.
Also, there are services out there that will monitor your queue depth and increase your dyno count for you. Or, you could use the heroku gem to do that yourself.
Depending on how long it takes a call to be dealt with it might be worth telling GAE to never spin up more than one instance. Sure, the occasional user will have to wait a couple of extra seconds to be dealt with, but you won't have to worry about cost.
I am not familiar with the internals of Heroku and don't know how they solve the problems I outlined. Maybe someone else can elaborate.