Who offered IaaS and PaaS before AWS?? That is revolutionary.
That was in 2007; S3 and EC2 were in 2006. The pace of innovation at AWS has declined, which is partially to be expected as it matures.
https://en.wikipedia.org/wiki/Media_Temple probably counts, too. They had auto-provisioned VPSes long before EC2. I'd also count VMware ESX.