有料のペイント/ドゥローソフトなら、4/8bitパレットを１色単位で減色/編集出来るよ。
価格が少し高めだけど、MacromediaのFireworksがおすすめ。
より高価なPhotoShopよりも、パレットの最適化/手編集の効率に優れると思う。