One optimization tweak later, all texture files now weight 75% less!
On the technical side, I included transparency in the palettes, rather than in the textures. While this means that a sprite with transparency is now limited to 3 colours (down from 4), this method also offers more versatility (and is more faithful to the classics).
Oh, and treasure!