Although a lot of us are upset about how this was handled, I'd suggest testing how much you can optimize first. If that doesn't help, I have a couple of suggestions below. Here is my own plan:
1. Start with optimizing settings. Things like reducing max idle instances and lowering the rate on low priority task queues to reduce spikes.
2. Set a minimum instance commitment to take advantage of the lower cost for committed hours.
3. Optimize the datastore. My biggest cost is in datastore ops (mostly writes), so I'm looking at adding (indexed=False) to model properties that I don't query on, and using memcache more often.
4. If the above gets me back to a reasonable cost, then I'm staying. If not, then I'm looking at
AppScale and
TyphoonAE. Both are open source solutions that allow me to run GAE apps on other platforms. They're not battle tested, so I expect to have to pitch in with a few bug fixes, but I know that they've ran some apps successfully (TyphoonAE says they've ran the PubSubHubbub server successfully, which happens to be one of the apps I run as well). In terms of server hosting, I've used RackSpace and Softlayer, and they're both really good.
I hope this helps. I have a huge amount of code which makes re-writing my apps almost impossible. If your code base is still small, you might have other options as well.
Waleed
Regarding hosting options, I am looking at rackspace since there are many successful businesses outside are using it. Now looking at if I should switch to node.js or keep running python on the new server.