I've found that on many types of data, xz -2 is twice as fast and compresses better than gzip -9. Of course gzip -1 kicks the pants off xz but there's absolutely no reason to use gzip at its higher levels, nor to use bzip2 at all. And if you want fast, LZO does it better -- the lzop tool provides a typical unix compress interface.

Using 50MiB from a tarball I had lying around, best of 3:

     prog    time(s)   size(%)
    gzip  -1  1.703    38.7
    gzip  -9 14.670    35.1    (worse than xz -1)
    bzip2 -1  7.714    34.0
    bzip2 -9  8.035    31.4    (worse than xz -1)
    xz    -1  6.278    31.3
    xz    -9 42.445    22.7    (best compression)
    lzop  -1  0.670    46.1    (fastest)
    lzop  -9 18.144    38.0