O gzip e o bzip2 são funcionalmente equivalentes. (Era uma vez um bzip, mas parece ter desaparecido completamente da face do mundo.) Outros formatos comuns de compactação são zip, rar e 7z; esses três fazem compactação e arquivamento (compactando vários arquivos em um). Aqui estão algumas classificações típicas em termos de velocidade, disponibilidade e taxa de compactação típica (observe que essas classificações são um pouco subjetivas, não as leve como evangelho):
decompression speed (fast > slow): gzip, zip > 7z > rar > bzip2
compression speed (fast > slow): gzip, zip > bzip2 > 7z > rar
compression ratio (better > worse): 7z > rar, bzip2 > gzip > zip
availability (unix): gzip > bzip2 > zip > 7z > rar
availability (windows): zip > rar > 7z > gzip, bzip2
Como você pode ver, não há um vencedor claro. Se você quiser confiar em programas que provavelmente já estarão instalados, use o zip no Windows (ou, se possível, arquivos auto-extraíveis, pois o Windows não é fornecido com nenhum deles) e gzip no unix. Se você quiser máxima compactação, use 7z.
O Rar também tem desvantagens que, até onde eu sei, não existe software livre que crie arquivos rar ou que possa descompactar todos os arquivos rar. Os outros formatos têm implementações gratuitas e nenhuma reivindicação de patente (séria).