I would, but if it's a "valid concern" that gzip is a few hundred KB larger, and the community would not graciously receive such work, there's not much point, is there? :-)
Seriously, though, if I understand gzip correctly, it uses deflate/zlib internally. Why, in that case, does /bin/gzip not (dynamically) link against libz? If a first step was fixing that, a second could be linking dynamically against libbz2 and 'liblzma', and making it all compile-time configurable.