I was an early user of Google too, and I don't remember the search results being any better than AltaVista (the dominant search engine at the time) or any of its other competitors.

Google was just fast and ad-free, unlike AltaVista, which was ad-infested and slow. That was the attraction for myself and the other people I knew who used it.

Perhaps we used to search for different things. AltaVista allowed far more control over operators and filters, but invariably I would have to dig much deeper in ther results to find what I was looking for. On google it would be there on the first page.