Jain zu allem....
Paint speichert alles entweder als große Datei oder in ner schlechten Qualität, am besten GIMP oder Paint.NET runterladen, es geht auch Photoshop oder Fireworks, bei allen aber kann man dann das Format auswählen, die Qualität angeben und daraus die Dateigröße erschließen.
Am besten ist meiner Meinung nach PNG32 oder JPG (JPEG). Das sind die kleinsten und qualitativ besten Formate, Adobe Fireworks speichert diese Dateien im Vergleich zu Photoshop in guter Qualität und kleiner Größe.
Meistens kommt es auf die verwendeten Farben an, es gibt aber auch noch andere Faktoren, die da eine Rolle spielen, z.B. der Farbraum (RGB oder CMYK) und die Optimierung für die Browseranzeige.