mtpaintで縮小したときの画質が悪いとのことですが、JPEGで保存するときのQualityとかの問題では？
また、MS　Paintで使用されている圧縮アルゴリズムは、いろいろためした人によるとどうやらバイキュービック法とのことなので、それで試してみては？
ちなみに、JPEGで保存するときの品質は、メニューの
Image>Preferences
からのPreferencesウィンドウのFilesタブをクリックし、そこの”JPEG Save Quality (100 = High)”の項目で変更できます。

通りすがりに、ご意見、アドバイス有り難う御座います。

処理の設定は「最近隣法」で行い、同じピクセルにした物で、すべての方法を試している訳では有りません。と言うか「Linux」

がどの様に処理するのかが、良く解っていません。

何せLinuxに手を出して3日目で、「超」が付くほどの「Linux」初心者ですので、非常に助かります、有難うございました。
　
参考にさせて頂き、今後色々と試して行こうと思います。