This is how I added species support for Scerando's shadowtrooper to save space, as you can select the 7 armour colours, and 7 glows for each, for the head, torso and legs. (49 heads, 49 torsos, 49 legs) and it's less than 13MB in size
Could you upload the pk3 so we could have a look at it, or take a screenshot of the folders' contents. The extenstion only really matters in the .skin file if you have more than one texture with the same name in the same folder btw, most people just keep it as .tga, even tho their textures are jpgs
They don't have to be 256x256, most icons are 128x128, they just have to be to the power of 2. And they don't need to be jpg, but I think that's just most common.
@Marcus if you looked at the textures themselves, you would see how much work was put in; I would love to see you make a better skin that this if it's as bad as you say it is. And thanks for the map, Agent!