Да, это довольно неизбежно.Основное свойство, которым вы хотите управлять, чтобы повлиять на это, Graphics.InterpolationMode.Высококачественный выбор, такой как Bicubic, добавит много цветов к измененному изображению.Попытка вернуть 256 цветов приведет к зернистому изображению.Вместо этого вы можете использовать NearestNeighbor, чтобы уменьшить количество добавляемых цветов, но в итоге вы получите блочное изображение.
Вы можете попробовать кодер GIF, он также вынужден повторно сэмплировать изображение до 256 цветов.Он использует алгоритм дизеринга.Но, как правило, приводит к появлению шероховатых артефактов, которые становятся заметными, когда изображение имеет большие области схожих цветов, например голубое небо.Там нет никакого магического лечения за исключением просто не повторной выборки обратно.Нет никакого смысла делать это с замечательным оборудованием, которое у нас есть в наши дни.