But was Erik actually talking about "compressing" the binary machine code, or just re-writing the source more efficiently?

If you're actually going to compress the binary in ROM, then you're going to have to add overheads of the code to do the decompression, the time taken to do it, and somewhere (RAM) to save the executable (decompressed) code.