1. Таки да, палитра дефа лежит в обычном RGB в начале файла. Загрузка-выгрузка штука несложная.

2. Все же лучше использовать фотошоп (или таки его аналог, да).
Не вижу никакой необходимости в ручной работе: макросы на применение корректирующих слоев либо отдельной для каждой группы цветов модификации HSL. По крайней мере, когда мне понадобилось перекрасить пару монстров, это нормально работало.
А еще лучше использовать спрайтшиты. Из той же самой heroesland, хотя там вроде перекосили палитру.

3. С другой стороны, можно загружать измененную палитру в рантайме, чтоб, например, нейтральные замковые юниты носили черное обмундирование вместо синего, лол.