I have a Geforce 5200, so assume most of the modern geforce cards will do this.
Using the standard default for TV of 800x600 via s-video gives me a slightly grainy picture on my widescreen 24" TV (nothing special - I bought it from tescos!) using DVB-T (freeview). However, upping the resolution to 1024x768 gave a pin sharp picture, just as good as my Pioneer set top box.

Not sure why you would get a grainy picture, but displaying PAL using a 600 line modeline is a bad idea that usually results in a picture that is not very sharp. This is because the myth will scale the PAL content to fit on the display (scale 576 to 600). The video card will then scale the display to the s-video resolution (600 back to 576) and loose a lot of sharpness in the process.

1024x768 is probably not ideal, but at least 768 factors well for 576 line content (4/3), so the scaling probably wont effect the vertical resolution as badly (and you get the added bonus of an improved horizontal resolution).

Your best bet would be to use a modeline that matches your content (and the TV standard). I use the following 720x576 modeline:

I've recently discovered that switching from 800x600 to 640x480 on an NTSC TV substantially improves the picture, with better color saturation and possibly sharpness as well. I've tried 640x480 in the past and didn't see much difference, but that may have been the result of a bad mode line...