If you're using the included video out on a PC video card, that's part of the problem. Those things are giant pixel mashers that do all sorts of nasty scaling to "just make it work".
If you bypass all that by using native TV timings on the VGA port and an outboard RGB to NTSC converter, you can often get much better results, but it takes a lot more set up. You'll also then be limited to 640x480 (and interlaced, at that), but the TV just can't do any higher. Even if you have your resolution set higher right now, it's scaling it down to 640x480. It's also probably underscanning it quite a bit which just further crushes it down and reduces usable resolution.
S-Video will look much better than composite still, especially on stuff with lots of sharp edges. Right now, though, go in and check to see if your drivers have an option to switch the TV out from S-Video to composite mode. Properly generated composite (with all the right filters) does a better job than passive S-Video to composite conversion like those little cable dongles do. You'd still use the dongle as an adapter, but it would be doing no conversion since the card would already be outputting composite. This may help a little, at least.
If you can find a TV with component inputs, then that's a great option, though a GOOD S-Video input (emphasis on the GOOD part) can attain comparable quality.