I tried to benchmark a little. Archivers were limited to 512 Mb.
Timings only in the second test. Precision is kept 1 Mb/10 seconds
intentionally.
There are many comprehensive benchmarks, but I tested nearly the
last versions.
OpenOffice 2.0.2 sources, 1209 Mb (there are several .gz and
bzip2 has similar compression rates (except maybe for multimedia
files, which isn't the case) and 7zip/LZMA usually compresses better
than RAR.
7zip isn't installed by default in any distro AFAIK, but at least it
open source.
RAR would be my last option...
I tried to benchmark a little.