Для максимально качественного преобразования нужно использовать либо Adaptive Paletted либо Optimized Palette.

В результате выбора этих опций производится расчет палитры так, чтобы она была максимально приближена к изображению. Но все равно 256 цветов может не хватить и будет видно явное нарушение качества. Побороться с этим можно использованием опций коррекции ошибок.

Коррекция ошибок основана на обмане зрения. То есть, если цвет не удается поместить в палитру, то он искусственно создается одним из двух методов. Основано это на том, что если два пикселя разного цвета находятся рядом, а вы смотрите из далека, то видите другой цвет. Первый способ это Ordered, если цвета нет, то каждый пиксел несуществующего цвета заменяется на два других, которые на удалении дают этот цвет.

Второй метод это Error Diffucion. Результат будет лучше, так как для получения цвета будут использованы несколько пикселов. Смотрите результат конвертации того же изображения.

Невидно четких переходов, как в предыдущем варианте, при некотором удалении или уменьшении масштаба выглядит практически как оригинал.