If you're going to continue using the yellow connection for video, not much more to try beside trying to adjust the frequency as MacDude suggested above.
The S-Video provided on that Apple video adapter would give you a little bit better picture than the composite connection, but not much.
What you're basically doing by using composite is similar to watching one of those youtube videos on your computer that are 280 or 320 and blowing it up full screen - pretty yucky.
Been a few years since I had one of those TVs.
That single yellow plug you're using for the video is called a composite connection.
The maximum it will input into the TV is 480i. Don't care what it says in Displays preferences. The port on the TV is only reading 640x480. The red and white are the audio connections only.
Best way to do it, would be to use component. That's the red/green/blue connections. But to do that, you're going to need a converter -
not an adapter. All those VGA or DVI to component adapters you can find all over the place for less than $10 only worked on a few older ATI video cards - primarily the All-in-Wonder cards. They will not work on anything else. Once again, you need a
converter. You'll still use the red/white for audio.
The component connection will handle 720p and 1080i.
You'll need:
mini-DVI to VGA adapter to plug into the Mac
a VGA cable from there to the converter
a VGA to component converter box - something like this -
link
then connect the component cable that comes with that converter to the TV.
That particular box gives the specs of the VGA resolutions it will accept and says it will output 480p, 720p or 1080i. The few reviews sound like it's a decent box for it's $30 price tag.
Although a little hard to find, this type of converter should range in price from that $30 to maybe $70.
Harder to find, and don't think I would go there, is a DVI to component converter. These typically allow higher resolution inputs into the converter, meaning you
should get a better output, but you're not going to find one for less than $150-$180.
I did use one of these quite a few years ago, and the picture was substantially better than composite or S-Video - ymmv.