The declining quality we notice is likely because Google is getting better at serving everyone else. It's only going to get worse for handling off-mainstream queries, and it won't matter for most people who aren't looking for an obscure forum post from 1997.
Sure HN notices this first, but for sure the "regular people" are not far behind.
Still, there are no good alternatives -- yet. You can bet if Google is the new Altavista, then the new Google is just over the Horizon waiting to steal their ad revenue...