For some reason, OS X seems to be reluctant to output 1080p to TVs, and usually defaults to 1080i. At first I thought it was the cable (a 50′ HDMI cable purchased from Eforcity for $40), but that turned out to work perfectly. The problem was that the only option for 1920×1080 that showed up in the Displays System Preference was interlaced.
However, when I checked the “Show displays in menu bar” option, lo and behold, there were two options. Both of these looked exactly the same, but when I switched between them, I found that one was 1080p and the other was 1080i.
I found this to be the case on both Macs I tried it on, so check your TV and make sure you’ve got progressive mode enabled!