Inspired by Yandex, I've made Faviconize Google user script, which adds favicons to the Google's search result page.
User script: http://userscripts.org/scripts/show/58177
Chrome extension: https://chrome.google.com/extensions/detail/fijobgpmmkilncag...
Yandex appears to load the favicons from their own cache. If your extension hits the sites themselves, you're leaking the fact that they are appearing in a person's search results to the target sites... and maybe even the query terms, via the referrer header. You should probably mention that fact to users who might not deduce it themselves.
My script takes the favicons from Google. http://www.google.com/s2/favicons?domain=news.ycombinator.co...
Overall it feels like a really nice design, but I can't pinpoint why exactly. Might be because Google's strayed so far from the original and simple interface.