Hi all, thanks again for a lot of good inputs.
We ended up evaluating SEGGER's emCompress vs. Heatshrink. Both were potentially valid, but for our particular combination of memory and speed requirements, it looks like Heatshrink may be the better option (and open source). Thanks again for the great suggestions!
Martin