I've found that, if you want to make responsive apps on GAE, you must use memcache. At any scale. Personally, I gave up and left for better options. The generous free quotas aren't worth the trouble.

I hear they've improved latency since I left, so take this with a grain of salt. I'm still not going back any time in the next few years, though.