In Photoshop it is a pain in the neck. It is dead easy to reduce to two colours - but getting 4 is tricky.

Yeah, I know what you mean. This is one of the reasons I stick with Paint Shop Pro, as it's much better suited to doing indexed-color reduction. Doing things like Quake1/2 textures is nearly impossible in Photoshop.

I never understood this. I don't see why Adobe has to make indexed work so difficult. And it literally becomes a problem where I work, because our art department likes Photoshop. Every time we ask for a 16-color Windows icon, we get something that uses something other than the 16 Windows Palette colors.