In Photoshop 6 anyway... Image->Mode->Indexed Color and play around with the options until you get a good quality color reduction.. and keep in mind you'll probably have to use remap palette, unless you create a custom palette, probably using Palette Suite