Well... not all of that is necessarily true.. You can get a .png icon and slap it on a background and save it as a .gif without loss of quality in the icon or any other part of the image. I've done that multiple times with it turning out exactly as I wanted it to.
Don't think as .gif and .png as the same. .png is lossless image quality, that is, no aliasing. You can read all about the .png image format from the png site:
http://www.libpng.org/pub/png/pngintro.html Just remember that .png as one main advantage over .jpg, you can have transparency with a .png but the image is almost always bigger than a .jpg with a compression quality of 12 in photoshop.
If you're looking to optimize your images of something then you should stick all of your icons onto a (the term escapes me) single image file and place your icoms on different areas of this single image file. This is so there is only one http request instead of a dozen on a web page.
As for image compression, use .gif with a transparent background. That's the best image compression you'll get while retaining some if not most of the image fidelity. You can just use photoshop for that, I'm not aware of a different program that deals with image compression..