3
I'd guess you are using GD 1, which generates very ugly thumbnails (but has the benefit of being on most systems). GD 2 is an improvement, but NetPBM and Imagemajick are much better, so switch over if you can.
Another possibility is that you have set the quality setting for thumbnails set very low, you can check in preferences for that module, if it allows it. Set it to something high!