Also Gif kannst du schonmal vergessen. Alles was Gif kann, kann PNG auch, nur besser. Mal abgesehen von Animationen, aber dafür gibt's ja dann Motion-PNG. Gif ist jedenfalls ein absolut veraltetes Format, dass man besser meidet.

Neben PNG und JPEG wäre noch JPEG2000 empfehlenswert, welches dank Wavelet-Kodierung im Vergleich zu JPEG eine höhere Kompression bei gleicher Qualität bzw eine höhere Qualität bei gleicher Kompression bietet. Leider ist das Lesen und Speichern von JPEG2000 z.B. über Photoshop nur mittels Plugin möglich (jedenfalls war es bei CS3 noch so, keine Ahnung ob CS4 oder CS5 das nun unterstützen), und das Format ist allgemein noch nicht so weit verbreitet. Es findet aber z.B. Verwendung im Format für digitales Kino, ein Film im Digital-Kino ist also (M)JPEG2000 kodiert. Einige Video-Schnittprogramme setzen auch auf das Arbeiten mit JPEG2000, weil es jedes Bild einzeln codiert (also nur I-Frames und keine GOPs anlegt) und dies die Arbeit erleichtert und die Kompression dennoch einigermaßen hoch ist.

Daneben kann JPEG2000 auch verlustfrei komprimiert werden, ähnlich wie PNG.

Welche Programme JPEG2000 speichern und lesen können musst du aber selbst herausfinden. Google hilft dir sicher weiter.