Maybe I was just too young to know better, but I seem to remember AltaVista being pretty decent. My internet was super slow back then anyway, so the search latency probably didn't make a huge difference.