At the risk of over-promoting myself, I got fed up with google's default search a few months back and (re)wrote a command line client, called gnugol, to make my life simpler and faster - and far less annoying again.
It works the command line and in emacs.
The latency improvement is remarkable. The S/N ratio is nice too.
Originally, it was a client/server protocol that ran over udp, I've been thinking of resurrecting the server piece, possibly using sctp, as I think latency can be further improved with a persistent connection for search.
Google's search IS so fast that in many cases the RTT for initial TCP setup dominates the entire session - I can get a 50ms response for a query located 2ms from google, and 200ms (at best) for one from Colorado.
I would certainly like more people to give the idea and tool a shot.
Gnugol also supports bing and a few other search engines - I thought what I wrote here about stackoverflow's interface, vs gnugol's to be pretty damning.