VPSes were usually not cost effective either if what you wanted was a big pool of storage space. The big growth opportunity for S3 was the companies that would otherwise run their own SANs, not the startup that was going to run on a couple of VPSes or shared hosting otherwise.

Even the startups that grew, they might start on a VPS provider, but outgrow them. S3 managed to scale with them and retain them as customers.