Having inherited a large legacy codebase running on App Engine and powering a successful business, I see the biggest danger with App Engine as being the lock-in. We're on App Engine and we're not going anywhere, because it'd be too big of a project to move somewhere else. There's one open source project I know of that lets you run an App Engine project on another server (Appscale), but it's hard to know how useable it would be without the overhead of getting everything set up, and surely there are plenty of dark corners you'd encounter along the way.

Since App Engine comes with a proprietary data store, ORM and task queue built in, skipping the Appscale compatibility thing and just porting a large application to run on another platform would be a herculean effort. The data store models and everywhere in the application code that they're queried would need to be re-written for a different ORM, all of the data would have to be migrated to a different store, and all the background tasks and methods that trigger them would need to be rebuilt. This would be thousands and thousands of lines of hand-edited code changes, before even thinking about how much time would need to be spent verifying all of the changes.

At least with Heroku the magic is mostly around deploying and scaling the various pieces, rather than providing a lot of application level libraries that lock you into the platform. Porting to another platform likely would require a bunch of configuration management and some deployment scripts, but fairly limited changes to the application code itself.

As mentioned before, there is AppScale which will let you avoid the lock-in if you so desire. AppScale has been around for quite a while, and it has been sponsored by Google, but it is an independent company and an open source project. AppScale has been running customers application reliably for few years, with Datastore load of up to a quarter million of transactions (and this is an old white paper).

AppScale will allow you to move your application (unchanged) and still reap the benefits of the App Engine model, autoscaling and all. I still believe App Engine benefits trumps any other PaaS out there.

The easiest path off Heroku to self-hosted is probably Cloud Foundry: one of the inspirations was Heroku and several of the Cloud Foundry buildpacks are soft forks of Heroku's buildpacks.

Generally we find that any buildpack written for Heroku will work with Cloud Foundry without modification. With a little extra engineering you can create a buildpack that will run in a fully disconnected environment.

Disclosure: I work on the Cloud Foundry Buildpacks team on behalf of Pivotal.