Как создать палитру цветов для bmp изображения?
Вот тут кажется много полезной информации с кодом:
www.enlight.ru/demo/faq/smth.phtml?query=alg_clr_dith
Ключевые слова: Кластеризация (Quantization), Dithering.
Можно, даже, взять усредненную (универсальную) палитру, но результат будет не всегда хорошим.
Ваша палитра вышла не такой плохой на первый взгляд как вы подумали, однако я вижу что изображение, построенное на ее основе, не использует яркие цвета, вероятно есть ошибка в алгоритме.
Поиск цвета в палитре нужно вести только не только по яркости. Скорее по сумме квадратов отклонений по каждой цветовой компоненте.
И еще - у вас не сортировка по яркости, у вас один проход с перестановкой, он не дает полную сортировку.
Скорее всего из-за этого у вас и получилось такое тусклое итоговое изображение. Но яркость - все равно не то, синий и красный цвета будут одинаково яркими, но совсем разными.
1) Самый простой вариант, мне кажется, случайно выбирать цвета (например случайные пиксели изображения)  и искать ошибку отображения (сравнивать или со всеми пикселями или с небольшой частью, 1% например),  потом следующая итерация с небольшим изменением и так далее пока не будет достигнут минимум ошибки, очень просто, в цикле перебирать варианты. Мне такой подход нравится, что нет математического анализа, работает компьютер, программист отдыхает ))
2) Высокое качество картинки из 16 цветов, почти неотличимое от оригинала, достигается добавлением цифрового шума, недостающие цвета получаются слиянием цветов рядом расположенных пикселей, и градиенты пропадают, алгоритм, конечно сложнее
3) Посмотрел на картинку что дал ваш код, её можно улучшить покрутив контраст, сделав темные участки темнее, светлые светлее. Алгоритм изначально теряет контрастность, усредняя слишком большие участки изображения.