Google became popular through word of mouth, so they must be doing something right. Yahoo provides better search results? Yeah right!
If memory serves me correctly I may have stumbled upon Google.com back in 1998. Maybe late 1997, but don't quote me on that. Someone else had used it at the TAFE library (Australian will know what TAFE is). I was pleasantly surprised that when I done a search for any topic I would find relevant results. It was pretty damn impressive actually. Up until then I would use every search engine I could find and had bookmarked and it was a hit and miss affair. Nowadays though, upon reflecting, I'm not getting the quality search results I was used to. Maybe it's to do with the effects of the efforts of SEO, or rather Search Engine Manipulation.
I used google back when it was in beta, it was a breath of fresh air from the other search engines/directories at the time.