Я бы сказал, что PNG, вероятно, лучшая ставка. Более современные браузеры (читай: не IE6) понимают 8-битный альфа-канал, который он предоставляет, тогда как GIF-файлы просто имеют ключ прозрачности.
Зачастую в наши дни узким местом на сайтах является не размер изображения (ни в размерах, ни в данных), а количество запросов, необходимых для загрузки страницы. Более современные дизайны сайтов пытаются упаковать как можно больше изображений, используя такие методы, как CSS Spriting (woot.com, большинство из Google). Другим узким местом часто является неправильная настройка кэширования, что заставляет возвращающихся посетителей перезагружать кучу вещей.
Вы увидите, что различные страницы Google кэшируют все, что могут, и уменьшают количество вещей, которые необходимо загрузить на одной странице (объедините все Javascript-коды в одну, все таблицы стилей CSS в одну), чтобы браузер выполнял 2 и 3 запроса. вместо 15-20.
Я бы пошел с PNG и посмотрел на спрайты CSS и кеширование как на альтернативную оптимизацию.
См. здесь для примера спрайта изображения, используемого на главной странице Google.