I sorted the textures and down-converted all the 2048 and 4096 to 1024, and the 1024 to 512. It's not a perfect solution but the texture pack size is a serious issue. Even at 72MB there will be admins who won't use it but this is doable as a working model.
I passworded my coop server and I have this running on it if you want to see it. Pass is the same as before. I'll work out the rabbit issue in the next couple of days and clean up any issues. If you get a chance pop in and let me know if this vastly improved things for you.
As a point of reference here's a visual for what I've done:

Frome left to right let's number them 1, 2, 3, and 4.
Number one brute is default skin.
Number two brute is downconverted to 1024 and the file size went from 50MB to 683kb. This is the version on my server right now.
Number three is your default uber-large skin directly from the 600 MB package.
Number four is a further test where I went to 512 size and the texture went down to 171kb. Using this I can get the mod in under 45MB or a little less. (Edit: I think I can get that down to ~20MB honestly)
As you can see the tradeoff for perfect visuals is well worth the incredible savings in file size.
**Small update: reworked the code and fixed the rabbits and birds so they work right. The only exception is the biterfish. Since the biterfish school spawns the fish dynamically I'm having issues getting the skin to replace online. (I wonder if this is related to the CanSeeMe thing?) Anyway I may just forgo the biters instead of hacking some terrible thing up to get them to work since they are so small and fast. Oh and I tested using 512 textures and the result isn't satisfactory. There's a big loss in quality from 1024 to 512 so you were right in that 1024 is the lower limit. It's fine, I played MH-SoccerStaduim (sic) and had hundreds of high skin monsters in visual and there was no lag.