back then search was possible but excruciatingly slow - you could use other net services like WAIS or Archie but it was the sort of thing you'd leave running the background. Plus those services were terminal based so navigation was tedious if you were on dial-up. Having all that stuff classified and aggregated on one website was a godsend. The amazing part is that in its early incarnation it was so simple anyone could have done it. Literally, just links and descriptors. I've often wondered if attitudes of and towards Jerry Yang have something to do with the extreme simplicity of how Yahoo started out, and the 'right place right time' versus any definable innovation.
I never, ever thought of Yahoo as a search engine - if I did a search there, I assumed I was searching their internal catalog rather than the whole internet. Lycos and Altavista were the search engines of choice, while Yahoo was the homepage where I went for aggregated content. Then one day I tried Google and never went back.