Use xz. Debian, Gnome, Archlinux, Gentoo, Fedora have all switched to xz, and for good reason. I expect xz will offer a 20-30% reduction in file size. That will add up quick.
I did a little experiment with the american-wordlist-insane wordlist and sorting in the interim. I used msort which does a case sensitive sort[1] and sort which does not. Here are the results:
6830085 insane.msort
1461684 insane.sort.xz
1376548 insane.msort.xz
[1] Zebra comes before aardvark