bzip2 generally compresses better than gzip, but it takes for-ev-er on my A3000 :-) I was leaning towards lha at first, but zoo is faster and lha is considered non-free by Debian. I looked at the license and wasn't enlightened as to why...perhaps it's just not explicit enough?
I think I'm going to use zoo.
bzip2 is slow as heck indeed.
Lha might be considered non-free because of the patents on the LZW algorithm. Was it Unisys trying to exploit royalty rights to LZW before its patent ran out? This was a few years ago. I could Google it and find the answer, but then again so could you

If you were around back in the day you probably recall that zoo was not an uncommon compression format on BBSes and on the Amiga (and UNIX and...). I'm surprised to see that it still holds up well.
-t