|I agree with Derek on Super Media Converter, it's free and one of the best.|
When you reduce a video from a higher resolution to a lower one, of course it's going to loose quality.
A graphic card with 32 Meg's of memory is way under par for trying to view 1080 HD videos. I'm not going to get into why it can't do 1024X768 videos, there are way too many variables such as file format, compression ratio, etc.
bottom line, you need a better video card, or download Super and experiment with resolution and compression until you find a good balance between what your card will play and what's acceptable quality.