If you have Photoshop, and the number of colors on your GIF is less than 256, then I believe that Photoshop can optimize the palette (or so I hear) used by the GIF so that it will lose as little quality as possible. I don't think that MS paint has this ability.