Funny thing is I recall using Google from the very day I first saw it come across Slashdot -- probably late 1997 -- before they were incorporated even... but I also recall that at some point around 1999 I actually switched back to using AltaVista or something similar for a bit. Because I preferred the search results I got.
It was actually a more competitive situation than people might remember in hindsight.
The big difference is that Google made it through the .com crash filter better than anybody else. That and they kept the good will of their customers by keeping minimal and straightforward and (for a while) ad free.