I have a 32x32 favicon (in .ico format) that shows up fine in Firefox 3.6.12 and Chrome 5.0.375.70. But in Internet Explorer 7.0.5730.13 it looks terrible. It also looks bad in Windows Explorer (XP).
(Hmmm, I can't upload it - perhaps .ico format is blocked?)
(It's not IE8 but there is no other tag)
Check out this question on Stack Overflow, https://stackoverflow.com/questions/4031718/favicon-is-pixelated-in-ie.
It looks like 32x32 pixel favicons look much better in IE7 than 16x16. The only down side is Chrome only supports 16x16.
Here is an article going in depth into how favicons work and what your options are, http://perishablepress.com/press/2007/10/17/everything-you-ever-wanted-to-know-about-favicons/.
It turns out that the solution, at least in my case, is to save in 32x32 .ico format but with the transparency turned off.
In addition - when I use this in MediaWiki it only goes wrong using the default name: favicon.ico. When I use a non default name, the problem goes away!
In Local Settings.php:
$wgFavicon = '<name>.ico';