そもそも、Google App Engine(GAE)とVPSサービスとを比較することじたい残念な話です。

VPSとしては派手な広告のおかげで知名度のあるさくらインターネットのVPSと比較してみましょう。（あまり安くないのですが、借りたこともあってだいたいの性能予想できるし)
月２・３千円の運用費と仮定してみます。

導入コスト

契約時にさくらのVPS 512だと、０円ですが、さくらのVPS 1Gの時点で、2,980円かかります。これだけで、１・ヶ月分の運用費かかりますよね。

GAEの場合まったくかかりません。

導入した時点ではほとんどまっさらと言ってよく
Javaサーバー動かそうと思えば、JDKのインストールから始めないといけません。
Webサーバーもノーマルで多少の設定は必要です。
慣れにもよるでしょうが、この手間だけで安く見ても、数ヶ月ぶんの運用費飛ぶでしょう。

メンテナンスコスト

VPSの場合、OSのアップデートは自分でしないといけません。
WindowsUpdateみたいなのが毎月きます。またWebサーバーやその他サーバーもたまに緊急のセキュリティー対策をしないといけません。アップデート作業そのものは少ないですが、たまにアップデートすると動かなくなるケースがあり、そういうの含めるとコストはかかります。

GAEの場合、サーバー側に関しては面倒をみる必要は一切ありません。PaaS(Platform as a Service)に分類されるわけですから当然なのですが。

スケールアップ・ダウンのコスト

例えばアクセス増えて、さくらのVPS 1Gから、4Gに移るとしましょう。
そうすると9,980円とまた数カ月分の運用費がかかります。
次に、アクセスが減って必要なくなった場合どうでしょう、ダウングレードしてさくらのVPS 1.5Gにしても
やはり、4,980円と初期費用がかかります。

VPSは柔軟性がなく、見えない所でコストかかります。

開発中のコスト

本サービス開始までの開発期間中を考えてみましょう。
頻繁な規約改定でなくなってなければ、２週間ぐらいテストはできるでしょう。
でもローカルでもテストできるでしょうが、ネットワークやCPUがカタログスペックより遅いVPS上で動作テストしないと、実際の動作を調べるのは難しいです。
そう考えると、おそらく１ヶ月ぐらいは正式サービスより先に借りてたりするでしょう。

GAEの場合、無料で使える時間が期間限定というわけではないので、開発期間がいくら伸びてもコストがかかりません。

Google App EngineとVPSとは用途が違う

VPSも昔のPerlのカウンターや掲示板動かしたり、あまりアクセスがないWebサイトをFTPでアップロードして
月数百円で運用する場合最適だと思います。

それ以外の用途ですとVPS使わず、Amazonだけでなく日本企業の大手がいくらでもサービスを提供している従量制のIaaS(Infrastructure as a Service)を選ぶべきでしょう。
IaaS上に作られるGAEのようなPaaSサービスは限定されたケースで最適です。