yeah hey okay so I was thinking:
there are two rows in the Quake palette which are nearly totally unused.
http://lunaran.com/pics/quakepal.png
One is that weird second blue row that grows in saturation as it brightens, the last row before the fullbright fire row. As far as I've seen, the only stock textures and assets that use that palette row are that one blue dragon stained glass window, and the textures from the dopefish secret. I'm fairly certain everything else that's blue uses the upper sky-blue row.
The other is whichever of the two very similar purple rows you could personally stand to do without. The only significant purple things in Quake are voreballs, runes, the one sky texture used everywhere, and the particles thrown when a spawn explodes. These two rows could easily be averaged/collapsed into one.
My point is, there's essentially two whole free rows of the palette that are up for grabs with minimal changes to Quake. Any mod can provide its own palette.lmp override in its basedir and get whatever mileage out of a partially customized palette the artist feels he needs, without really screwing up any stock textures or assets at all. No special engines required. The only thing that would really need to be included would be replacements for the voreball and end runes which make sure they're the same purple as the sky. (If you didn't mind voreballs and tarbaby dust being some other color you could even have three rows.)
However, there are additional costs: namely, assets for a palette-plus mod would no longer be shareable, because once you move them back to /id1/ or any other mod you'd wind up with blue and purple shit all over. That runs the risk of creating mutually exclusive asset ecosystems, and this community's been traditionally about freely sharing in that regard. Then again, we've all been using textures from Hexen and Alice and sundry sources with bad-to-passable palette conversions for decades and it hasn't turned anyone off, so an additional stock-palettized wad could easily be created as long as the losses wouldn't be too visually egregious. Plus, wouldn't it be nice to be able to use said Hexen and Alice textures with one or two rows of their actual palette brought with them?
Tool support would be a problem: not every common Quake editing app supports custom palettes. QE3 does (getting that editor to actually find the damned palette lump on disk is like obstacle #1 to getting QE3 to work at all), but others don't. TexMex, critically, simply has the stock Quake and Quake2 palettes hardcoded, and mickey vanished from the scene and took the TexMex source with him 15 years ago.
This might all be way too much bother for 32 extra shades of brown (lol), especially when engines exist that load full color TGAs, but it's something I've been thinking about.