What alternatives are there to GAE, given that I already have a good bit of code working that I would like to keep. In other words, I'm digging python. However, my use case is more of a low number of requests, higher CPU usage type use case, and I'm worried that I may not be able to stay with App Engine forever. I have heard a lot of people talking about Amazon Web Services and other sorts of cloud providers, but I am having a hard time seeing where most of these other offerings provide the range of services (data querying, user authentication, automatic scaling) that App Engine provides. What are my options here?
Amazon's Elastic Compute Cloud or EC2 is a good option. You basically run Linux VMs on their servers that you can control via a web interface (for powering up and down) and of course access via SSH or whatever you normally set up... And as it's a linux install that you control, you can of course run python if you wish.
I'd be more interested in seeing how App Engine can be easily coupled with another server used for CPU intensive requests.
I don't think there is another alternative (with regards to code portability) to GAE right now since GAE is in a class of its own. Sure GAE is cloud computing, but I see GAE as a subset of cloud computing. Amazon's EC2 is also cloud computing (as well as Joyent Accelerators, Slicehost Slices), but obviously they are two different beasts as well. So right now you're in a situation that requires rethinking your architecture depending on your needs.
The immediate benefits of GAE is that its essentially maintenance free as it relates to infrastructure (scalable web server and database administration). GAE is more tailored to those developers that only want to focus on their applications and not the underlying system.In a way you can consider that developer friendly. Now it should also be said that these other cloud computing solutions also try to allow you to only worry about your application as much as you like by providing VM images/templates. Ultimately your needs will dictate the approach you should take.
Now with all this in mind we can also construct hybrid solutions and workarounds that might fulfill our needs as well. For example, GAE doesn't seem directly suited to this specific app needs you describe. In other words, GAE offers relatively high number of requests, low number of cpu cycles (not sure if paid version will be any different).
However, one way to tackle this challenge is by building a customized solution involving GAE as the front end and Amazon AWS (EC2, S3, and SQS) as the backend. Some will say you might as well build your entire stack on AWS, but that may involve rewriting lots of existing code as well. Furthermore, as a workaround a previous stackoverflow post describes a method of simulating background tasks in GAE. Furthermore, you can look into HTTP Map/Reduce to distribute workload as well.
Microsoft Windows Azure might be worth consideration. I'm afraid I haven't used it so can't say if it's any good and you should bear in mind that it's a CTP at the moment.
If you're interested in the cloud, and maybe want to create your own for production and/or testing you have to look at Eucalyptus. It's allegedly code compatible with EC2 but open source.
AppScale
AppScale is a platform that allows users to deploy and host their own Google App Engine applications. It executes automatically over Amazon EC2 and Eucalyptus as well as Xen and KVM. It has been developed and is maintained by the RACELab at UC Santa Barbara. It supports both the python and java Google App Engine platforms.
TyphoonAE is trying to do this. I haven't tested it, but while it is still in beta, it looks like it's atleast in active development.