1) Самый простой вариант, мне кажется, случайно выбирать цвета (например случайные пиксели изображения) и искать ошибку отображения (сравнивать или со всеми пикселями или с небольшой частью, 1% например), потом следующая итерация с небольшим изменением и так далее пока не будет достигнут минимум ошибки, очень просто, в цикле перебирать варианты. Мне такой подход нравится, что нет математического анализа, работает компьютер, программист отдыхает ))
2) Высокое качество картинки из 16 цветов, почти неотличимое от оригинала, достигается добавлением цифрового шума, недостающие цвета получаются слиянием цветов рядом расположенных пикселей, и градиенты пропадают, алгоритм, конечно сложнее
3) Посмотрел на картинку что дал ваш код, её можно улучшить покрутив контраст, сделав темные участки темнее, светлые светлее. Алгоритм изначально теряет контрастность, усредняя слишком большие участки изображения.