I would argue against this lack of competitors you mentioned. We were using AskJeeves, Webcrawler, yahoo, msn, aol, Alta Vista, Lycos, Excite, Hotbot and a myriad of local service providers' homepages.
Google came much later than all of those, but it was better. How? I don't know, I was just a kid that got better results from Google than any of those other places.
Just because Google DESTROYED the competition before you got there doesn't mean that there wasn't any.