I spent some time looking at implementations of compression algorithms. As Bob pointed out, memory can be an issue with these libraries. I was hoping to say that zlib (gzip) would be suitable, but its minimum memory requirement appears to be 128K. There appears to be a way to reduce that, but it's still probably going to be too big. Later, better algorithms like bzip are going to be even more memory intensive.
I searched around and there are a large number of compression libraries that are free and designed for microcontrollers, with memory requirements in the hundreds of bytes (or even less!). None are as good as even zlib, but they are better than LZW (compress) and would be adequate. Also, more critically, they are designed to compress small amounts of data efficiently. The trouble then becomes finding one with a Java implementation, if we are planning to send the compressed data over the download or uplink.
Is this something worth pursuing?
-corey - AE5KM