Well, I'm not much into compression algorithms but you just need to find a better one that doesn't occupy much space. I remember powerpacker did a hell of a great job back in the day, have you tried that ? But it probably occupies too much space (you could try to use just the library and create some small custom code using it. Also some functions of the library could be ditched out).
Just an idea, I actually don't know the size of the powerpacker library either maybe it's also too big...
