I foresee that Google will become more money-hungry.
I also predict a lot more strict filtering of commercial sites on main search results as Google tries to promote it's merchant thing "Froogle", and of course to get people to pay for adwords.
With all of this happening Joe Surfer will notice that their Google isn't as relevant as it once was, and that news sites aren't always the best source of information for a search and begin to leave Google for Yahoo or MSN.
It's happened once before with an engine called AltaVista, noone ever thought they'd get moved either, until they turned their results into what amounted to a big, paid ad.
It's all gearing up for the Google IPO
And then there was
Teoma (my personal favorite at this time)
ps. AllTheWeb is going nowhere, it is a test site for the FAST engine which was bought by Overture, and Overture was bought by Yahoo... but I do like the FAST results more then Googles at this time.