7-zip has one of the best compression ratio / decompression speed ratios of the planet. Give it a try, compression ratio is a bit better than RAR, and decompression is faster. The linux port is p7zip.
Unfortunately you cannot use 7zip for streams like gzip or bzip2. 7zip uses LZMA as the compression routine, and it is possible to use just this high end compressor to get the best of both worlds.
This is how to get it: