CGI(Perl)で作成したビットマップイメージ(BMPファイル、という意味ではなく、
ピクセル毎の濃度情報の羅列、という広義のビットマップ)を、GIFなり
PNGなりに変換して、クライアントに返してやりたいんですけど、
そういうことって難しいでしょうか？

Cとかで書かれたPNGの圧縮ライブラリをPerlに翻訳するのは相当大変そうですが。
WindowsBMP形式で出力するのならPerlからでも簡単に書けますが…。
その辺の方法で、妙案を知ってる方、教えてくださいです。