As I recall (only as a contemporary user of search engines, and having no special knowledge), Google didn't just have a key innovation in PageRank (which was patented), but also took the idiosyncratic (at the time) architectural approach of horizontal scaling with commodity hardware (sometimes held together with Lego).
Altavista (supposedly) famously ran on a single "pizza box" Alpha server as a form of stunt marketing. There were other competitors that were invested in Oracle licenses and similar "big iron" approaches.
There was also the small matter of monetization. Google more or less refused to incorporate ads until they came up with a non-user-hostile capability. Their various competitors had advertiser-driven paid ranking, or "punch the monkey" banners, or other forms of shit sandwich users were supposed to accept. In general, the harder a search engine tried to monetize, the slower it's growth, unless they funneled their own revenue into marketing and advertising. When Google finally came up with their contextual search ads, users actually liked them and it was as if Google turned on a magical faucet that gave them money AND more users, and were able to scale to meet demand with more inventory.
