Edit their palettes.

If you look at my ramp image, there are a dozen or so colors which should remain the same (the solid grey and brown lines), but the rest of the palette contains differing shades of the civ color.
So, for a quick and dirty example, to make Rome's Red darker, you could open up Art\Units\Palettes\ntp01.pcx in Paint Shop Pro and choose "Adjust Brightness and Contrast" from the Color menu and crank the brightness down. Then choose "Edit Palette" and restore those browns and greys to their original colors. Then save your changes and that's that.
Of course, since the actual PCX image is a single pixel, you can't preview your changes decently so it's a pretty unfriendly process. I never got around to creating a decent method for editing the colors, so here's a quick alternative. Attached is a zip containing the 32 .pal files I created from the pcx images, the full ramps BMP I previewed above, and 2 "palette sampler" PCX files which are simply images with squares of the first 70 colors of the palette large enough to view without zooming in.
Open up one of the PCX files in Paint Shop Pro or some other program that understands .pal files. Then load the palette file for the civ you want to change into this image with the "maintain indexes" method and mess with the colors. When you are satisfied, save out the palette. Then open the ntpXX.pcx file from the game for that civ and apply your saved palette to it, again using "maintain indexes." Voila, you have a new civ color.
One other note, the histograph screen seems to use palette entry 7 (counting from 0) for the bar and palette entry 69 for the name, so make sure they have good contrast, unlike the dark orange/pink nonsense in the default ntp23.pcx
