I'm the author of appengine-magic. Rather flattered to see this on the front page of HN. If you have any questions about appengine-magic, or running Clojure on App Engine, I'll answer as best I can.
One thing to keep in mind: the latest version of the App Engine SDK is fully supported in the development (version 0.4.0) branch of appengine-magic (https://github.com/gcv/appengine-magic/tree/v0.4.0). I'm not quite ready to finalize and release this branch, but it's stable enough for in-development applications.
I recently built a simple site on this library (my experiences described here: http://www.thurn.ca/version_10_of_the_ackbar_blog_engine) and found it quite pleasant to work with, although there were a few Google API problems. GCV was also very helpful about answering my questions about the framework.
Clojure for GAE is nice. Its really cool that you can use this library with all ring-bases webframeworks (witch are basiclly all clojure webframeworks).
I don't now how python is for the appengine but clojure is much more better then java. The leiningen plugin that this library provieds is great.
Have you actually tried using clojure? Last I heard, relying on a large jar like clojure meant you spent 29 of your request's 30 seconds loading the jar and had only 1 second to do real work before GAE killed you.
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.
The Deadline (https://the-deadline.appspot.com) is written in Clojure and runs on GAE. If this problem still persists, somehow they must have found a way to deal with it.
I gave up on Clojure running on App Engine a year ago because I could not get the loading request time below 3 seconds. It is not as bad what you describe, but it was a problem. The loading requests happened frequently enough that users noticed the lags.
The example in the README is intentionally minimalistic: it relies on no external libraries. The Clojure ecosystem has several highly respected libraries for handling server-side templates, e.g., Enlive and Hiccup. All work fine with appengine-magic.
I'm still not sold on Clojure because of the syntax aesthetics but this is a surprisingly mature and complete project. Looks like it's been in active development for 8 months now.
Lisp syntax has always been a complain for new programmers that approach the language(s). But as I experienced myself, syntax is just syntax. Once you learn it, it does not matter anymore.
It's like learning a foreign language: it can have a (very) different syntax from yours and at first it can be difficult. But when you learn to speak the language fluently, it comes naturally.
I experienced this also in programing languages. I started programming in Pascal and then in C, for which the syntax is almost the same. Then I went to C++ and then Java. Both are Object Oriented languages, but they have some differences in their syntax as well. Still, no big difference.
When I started with Objective-C, though, the syntax was really confusing for me, even if it's an OO language. At first I was not able to understand even the sample code. But I was interested in it (for Mac development, iPhone did not exist yet) and now I find it more natural than Java (just because I am more accustomed to it since I use it every day, not because it's better).
So, when I learnt Lisp, I did not worry about syntax anymore. Sure, it's different, but we alwys have to learn new and different things anyway. Now I develop in Clojure and syntax is, again, not a problem.
I don't want to start flame war on lisp syntax again, but you may find clojure syntax more usable/readable after installing proper plugins for managing lisp code. Personally (as an emacs user) use highlight-parentheses-mode (each level of nested parens gets a different colour) and paredit (provides closing paren for each new you open, helps with joining/splitting expresions). I know there are also similar plugins for vim and eclipse (I'm not sure about paredit here). I was actually surprised when I started using them how much they help me.
I started emacs with clojure too. Paredit reallly rocks and is really easy. Some paredit function are so useful that I use paredit for other languages to here is the chatcheat http://www.emacswiki.org/emacs/PareditCheatsheet.
I use VIM to code in Clojure. I don't have paredit [1] but I don't find it really necessary, I can live just with rainbow parentheses and paren-matching (not to say that I would not find it useful if I had it).
[1] When I set up my Vim for Clojure development I made some research and I never saw it mentioned anywhere, so I think it's not available.
I am pretty sure there is paredit-like mode for vim, because I actually used it for some time. It seems that it is part of slimv [1] now, however I recall using it without setting up slimv.
One thing to keep in mind: the latest version of the App Engine SDK is fully supported in the development (version 0.4.0) branch of appengine-magic (https://github.com/gcv/appengine-magic/tree/v0.4.0). I'm not quite ready to finalize and release this branch, but it's stable enough for in-development applications.