For compatibility and speed, gzip is a winner. It's fast and it's everywhere (plus it compresses text well enough that it makes sense to use in place of non-compressed files).
For strong compression, there are better options than bzip2.
In a sense, bzip2 is "worse of both worlds".
Tl;dr, Thx for the summary
Try to extract xz compressed linux kernel on host with 128Mb RAM and 500MHz CPU. Then try to extract bzip2 - it will be very slow. IMHO gzip is the best option for old hardware or small virtual machines.