I think that Amazon being first in 2005/2006 helped a lot, too. Google now provides "primitives" through GCE. I think Google realizes that the future is GCE not GAE.

I think there's tremendous value still in GAE. To this day the fact that a company the size of Snapchat is able to operate on a PaaS, with virtually no ops people, is STILL a game-changer. The fact that it's still true 3+ years in is equally as impressive.

The narrative shifted away from PaaS for a number of reasons, but the value prop is still present.

(Disclaimer: work on BigQuery, a DBaaS, which is, in my opinion, is clearly the future)

But Amazon wasn't the first. The Sun Grid was first (launched in March 2006).

Sun Grid was more about batch processing across many machines, rather than individual VMs, wasn't it?

Plenty of people in the web hosting industry offered competitive x86 linux instances or dedicated servers, way prior to 2006.

I think AMZN deserves credit for delivering a price compelling option that delivered (1) elasticity (per hour billing) and (2) automation (API, available in minutes), among other things.

Exactly

Offer IaaS first, the PaaS. Google had it backward.

While AWS does have a small vendor lock in too, in the end it's still recognizable , I mean it's doable for example to move an AWS architecture to open stack without a major code rewrite. If you built your web app on GAE and GWT however, your investment to move it out of Google will be much bigger.