i have the same television, the Samsung with a native res of 1360 x 768. i had a similar experience as you did when i tried the different XBOX 360 settings, even had it claiming it was running 1080p. Game performance suffered noticeably (big difference in frame rate in Fable 2 for example, even running around was slower), but the most noticeable difference was the contrast and color saturation, which was much more severe, and there was a noticeable shift in display clarity/picture sharpness when the camera stopped moving or panning. My preferred display mode is without a doubt native resolution. Because you're asking the XBOX to render only what it needs to, and you're not asking the TV to take the work already done and then change that again on its way throughout the set, games display best, the rendering is smoothest, and although at first glance, the game seems paler or washed out, this just means you need to adjust the TELEVISION settings to your preference.
The reason i was looking into this is because i finally got my second HDMI cable from Amazon (i also run an Apple TV 2) and when i plugged my XBOX into the HDMI 2 port on the Samsung, i no longer was able to get the native resolution setting. At first i blamed it on the fact that Crysis 2 forced a dashboard update to my XBOX (which is NOT connected to the network) and i assumed that MS had dropped support for that feature and decided it was best for everybody to make their TV work harder... i was wrong. After reading this article, i realized that on the Samsung the HDMI 1 port is also a DVI port, and HDMI 2 is not. Now that i've relegated the ATV2 to HDMI 2 (it can't display my native res anyway), i now have everything back to ideal. So thank you very much for sharing a similar issue. In a round about way, it solves my problem, and made my day. Thanks!