I remember when Google appeared and literally can't recall anyone who thought it sucked. There statistically have to be some people who hated it. But everyone I knew was either on dial-up or low bitrate leased line and it was impossible to dislike that design.

I remember it too!

But not everyone was on dial-up. A lot were in dorms w/ (for the time) high speed connections or workplaces with it.

Remember at the time it wasn't clear that search was going to be the dominate pattern for how people found information on the web. It seems crazy now, but in the early days of the web, the space was small enough that a directory-style approach worked pretty well. It was Yahoo's directory that made it initially popular, not its search.

And so there was a fair bit of debate on which was better -- something like a directory + search (a la Yahoo!) vs just search.

It took a bit of time before search proved if it was done really well, you didn't need a directory.