Haverá trade off entre velocidade / taxa de compressão.
Você pode querer ver a postagem no blog, Comparação de compactação do Linux (GZIP vs BZIP2 vs LZMA vs ZIP versus compactação) . Os resultados do autor refletem minhas experiências gerais com os vários algoritmos de compactação. Preste atenção específica ao gráfico de descompressão.
O formato ZIP oferece a melhor compatibilidade de plataforma (o zip do Windows e do OS X suporta nativamente). No entanto, sua taxa de compressão provavelmente será pior do que a RAR.
O formato GZIP é uma escolha muito popular no mundo Linux. Ele fornece compactação muito rápida, enquanto as taxas médias de compressão. O Mac OS X suporta nativamente os arquivos gzip, mas no Windows você precisa de um aplicativo como o 7zip.
Os formatos BZIP2 e LZMA costumam levar muito mais tempo para compactar e descompactar arquivos, mas tendem a render taxas de compactação muito melhores. Eu acho que o OS X suporta ambos os formatos nativamente, novamente com o Windows, você precisará usar algo como 7zip.
O tipo de arquivos sendo compactados faz uma enorme diferença no tempo de compactação, na descompactação e na taxa de compactação e difere para cada formato.
Por fim, você precisará experimentar vários formatos e ver qual atende melhor às suas necessidades.