I'm looking at a live App Engine console for the Clojure app I'm working on right now, and I see cold-start JVM times varying from 3 to 10 seconds. Although this is a lot, with the latest App Engine, you can (1) pay $9/month to have 3 JVMs always running, and (2) your app receives warm-start requests which will cause a new JVM to start before it's needed.

In other words, your users should (almost?) never pay the penalty for a JVM cold-start. A single JVM stays around to serve requests as long as App Engine detects sufficient load to justify the resource usage.