Yep, I agree. I'm running a 25" TV and experience the same thing. For older MAME Arcade games, it looks fine, but any newer games or PinBall Tables (Visual Pinball and Future Pinball) the quality really deteriorates. And like you said, when I'm in Windows, I have a tough time reading the screen. (I had to re-register XP last week (added a new video card (GD MS!!)) and I could barely make out the numbers they provided, I was afraid I wouldn't be able to register it without pulling it out from the wall and hooking up a monitor to it!
For whatever reason, my video card (just bought last week, Nvidia GeForce 6200, 256mb) only allows me to run 800x600 or 1024x768, with the TV(?).
I love the size, but the quality definitely suffers. I've been strongly considering a 26" or 28" LCD mounted vertically, but the things are still too expensive to rationalize the purchase.
I'd really be interested in hearing a solution.