The exact same thing happened to me last week. On May 22 I was able to search the Internet like normal, and then I turned off my computer to go to bed. The next morning I tried using Firefox and found out that not many sites would load. I then tried Safari and had the same issue. I was able to search for something on google by typing a search term into the search box at the top of my browser, and it took me to the google page as you describe above.
However, when I clicked most links, they would not load. Some would, though, but only a few. After analyzing the links that did work, I realized that the sites that worked were https sites. Http sites would not work at all.
I had two things that updated on May 22 -- one was Adium and the other was Sophos anti-virus. The Sophos update was what caused the issue....but only because it must have had a conflict with AVG LinkScanner, which I had disabled a long time ago.
Before I realized that it was the AVG LinkScanner with the real issue, I turned off the web protection features on Sophos. I then refreshed some http sites, and it solved the problem.
However.....I did some more research and learned that AVG LinkScanner might be the real issue (even though it hadn't updated since Feb. and I had it disabled). I disabled it because I couldn't find a way to uninstall it. So I found this link:
https://discussions.apple.com/thread/4724011?start=0&tstart=0
And I uninstalled AVG Link Scanner, and after I uninstalled it, I turned back on the web protection features on Sophos anti-virus. The http sites still work.
I don't know if this is the same issue as I had, but it sounds so similar. Do you, by chance, have AVG LinkScanner, Sophos anti-virus, or any anti-virus program?