I'm older, and was there.

The word of mouth was real. I was working in tech at the time, and had Google recommended to me by a mate. I tried it, and it rocked. This would be about 1996, I guess, somewhen around then.

Every techie converted to Google, and we converted our friends and family. Sure they got media coverage, but remember at that time journos had very little clue about tech and relied on their techie friends and family for tips about what was going on. And, obviously, the internet was the big story at the time. I would absolutely not be surprised if it turned out that Google paid nothing for media coverage and were fighting off journos clamouring for interviews.

As far as I'm aware, PageRank was a completely unique innovation that no-one else had done or tried before. There may have been imitators, but they never got the traction that Google did.

By 2000, and AdWords and all the rest, Google was already the dominant search engine, at least with tech folks. SEO was just beginning around this time, because of that dominance.

And yeah, Gemini is an also-ran, despite all the money and tech expertise Google have thrown at it. It'll be interesting to see if they cancel it, like they have other products that have not done as well in the market (G+ being the classic case). Same for Meta (and, well, Meta).