Маштабирование всегда идет через интерполяцию. Самый простой метод "ближайшая точка" (судя по всему в GIMP, это "без интерполяции"). Более сложные бикубический, Lanczos, сплайны и др. Зачем это нужно?
Представь, что у тебя идет уменьшение в 2 раза по каждой координате (простой случай). Это означает, что квадратик из четырех точек в оригинальном изображении превращается в одну точку уменьшенного. Теперь ответь: какой цвет поставить, если в оригинальном изображении в квадратике 2x2 три точки черные и одна белая (предположим, что всё изображение состоит либо из 100% черных, либо из 100% белых точек)? Вот так и появляются оттенки серого (то самое твое размытие). Дело усложняется, когда мы уменьшаем в дробное число раз - нам как-то нужно "раздробить" точки (для этого и используют интерполяторы).
Если у тебя картинки с ограниченной палитрой, то попробуй сделать так:
1. Сохраняем палитру исходника,
2. уменьшаем RGB с бикубическим интерполятором,
3. уменьшенную копию конвертируем в заранее сохраненную палитру.
Это позволит минимизировать размытия (но потери, разумеется, будут).