Ну... PNG обычно не используют просто из-за избыточности, а не потому что это что-то вроде формата JP2, который вообще не каждый просмотрщик знает и Фотошоп (до какой-то версии или до сих пор) не понимает. Просто обычно 256 цветов вполне хватает (ИМХО для просто иконок его и должно хватать, немного странно, если нет), а если прозрачность не нужна, но хотят 24 бита, используют JPG, т.к. он хорошо сжимает. Но, так уж к слову, вчера буквально видел изображения в инете, они как раз в PNG и были, т.к. там нужна была достаточно качественная картинка (разрешение порядка 800х600), но требовалась прозрачность... Но я не знаю о целесообразности применения в общем случае, т.к. не совсем понял, на что непосредственно здесь не хватает GIFа и как повлияет использование PNG на траффик.
К слову просто тоже: недавно было дело сжимал небольшую картинку (то ли аватарку, то ли что-то в таком духе), что интересно: в 256-цветовом GIFе при требуемом размере она смотрелась лучше, чем в JPG - в последнем уже начинали выплывать артефакты, а количества цветов GIFа (там даже меньше 256 использовалось по факту при сжатии, что визуально не влияло на качество) вполне хватало.