Discovery in the mid-90s was excruciatingly bad. Google really did rescue the web in that regard.

I remember searching AltaVista for GNU’s website (at the time, they didn’t have their own domain, or weren’t using it) and I’m pretty sure I had to go to page 2 or 3 of the results to find it.