So I pulled out my hex editor and consulted the wiki about how the palettes are arranged. And after a couple hours I churned out a modified palette. That pesky red range was the first thing to be changed but I took a bunch of creative license with it so you may not like it as-is (there are some color glitches, but it overall takes on a different kind of style).
To use it, go in your UFO/GEODATA folder, rename your PALETTES.dat to a backup, and unzip this in there. The only palette modified is battlescape.
If anyone has any wishes for custom changes I can take the stock palette and make some modifications (this takes some effort, and I tend to want to edit only the 4 colors on the light/dark ends of the range). I expect everyone is going to want the Red colors changed to include some more saturation. However I am particularly fond of the TFTD silvered/patina color range which has a yellowish-gray appearance.
The screenshots are from x-piratez, the palette image was used as a basis to sample colors from to input in hex so its almost equal to the palette in the .dat.