I need some help, probably more along the lines of conceptual help more than coding assistance, but I need to devise a compression algorithm (and then a decompression algorithm that is good for compressing data types, like programs, appvars, pics, etc. And that is implementable on calc. I'm pretty sure that RLE isn't great for this. So, I'm thinking Pucrunch (but I know that there is no on-calc compressor) or LZ77. Am I right? Anything else?

Try using pixels in pictures. If you assign each command a Pixel code, you can store each command for less than a byte (maby).
Just an idea.

I know BatLib has some compression algorithms although you'd need to talk to Zeda to know how they work...

In my opinion, if you have a TI-84 SE or something, you should just archive everything, and not worry about compression. I have noted that to decompress a variable, you need to have as much room available during decompression as the compressed and decompressed variable added up...

That's not true of all compression algorithms by a long shot. Indeed, almost all stream-compression algorithms (as opposed to block-compression algorithms, if such things even exist) operate by building the compressed text and a dictionary (if necessary) while simultaneously scanning the plaintext. Such algorithms can therefore discard all of the plaintext already scanned at that point, meaning that the memory requirement is capped roughly at the size of the plaintext plus the size of the dictionary.