В нормальных фоторедакторах обычно есть несколько разных алгоритмов для изменения размера (bicubic, bilinear, lanczos, и т.п.). Пробовать разные алгоритмы, разные настройки. Но вообще для мелких картинок изменение размеров обычно работает плохо. Надо руками потом дорисовывать.