You said that it looks horrible with VGA did you try to adjust the resolution? That might be what the problem is although your not going to get the same quality out of VGA it still shouldn't look horrible.
Everytime I hook my TV up to my comp I have to adjust the Resolution to make it look right. Give that a shot and see if that helps at all