２日程悩んだ所で、(多分新しい)減色アルゴリズムを思いつきました。

• 色インデックス表に対して
• 各色から自分に一番近い色とリンクを張る
• リンク(色距離の逆数で重み付け)が多い色順に無効マークを付ける
• 無効マークが付いた色はリンク先の色からランダムで選ぶ (ランダムディザ風)

つまり色をノードとしてネットワークを作ってリンクが込み合ってる場所の ノードを間引きする感じ。
ネットワークに新しい色を追加するのも、ノードを辿っていけばコスト低めに 実装できそうな気がする。(多分)
一般的な減色アルゴリズムで重視する(色頻度の)ヒストグラムを全く考慮して いないので全然ダメな可能性もあるけど、それはそれでネタにはなるので、 とりあえず時間を見つけて試してみよ。^^;