When I had exactly the same problem (fuzzy HDMI display even with correct resolution), the problem was that the MacBook Pro was assuming that the monitor was a television, so it was using the "underscan" feature to map the 1920x1080 display into a smaller number of pixels on the actual display.
Apparently some/many televisions are set up so that the outermost couple of rows and columns are not visible, so the MacBook Pro "shrinks" the display by default to avoid losing this stuff around the edges. Unfortunately mapping a 1920x1080 display to (for example) the innermost 1840x1000 pixels results in terribly blurry text.
So look in the Display Preferences dialog for an "underscan" slider and adjust it to "off". This should only apply to HDMI displays. Most recent televisions based on LCD or Plasma technology don't "overscan" significantly anyway, so there is seldom a need to "underscan" as a correction.
For a few more words, see http://www.themacfaq.com/2010/11/11/understand-overscan-and-underscan/