The only reason I use AppEngine is because they offer free hosting. I guess we have to pay the price of using proprietary APIs for free stuff.
You probably wouldn't want to run Reddit on App Engine, but anything with medium traffic or decent monetization should work out just fine.
The only other caveat is that it may depend on what the app does and how you utilize the datastore. If you don't consider cost of the datastore when building an app, it could end up being expensive like you mentioned.
Don't try to go even cheaper, that way lies madness.