Well, people had been using hosted email from their ISPs, AOL, Hotmail, etc. long before Gmail.

Gmail came out and offered an insane amount of storage, basically toppling the regime.

So surely Gmail wasn't the one that surprised you. That ship had long sailed before then.