それは本当にそう思う。キャラクターのイメージが崩れるからねぇ。
加工OKでパレットの変更もOKだそうで。特にPCで書いた画像って256色が基準になってるから。
MD用にすると15色で一気に落ちるし。今回は原画が31色だったのでギリギリまでイメージを壊さずに15色に落とし込んだつもり。

とりあえず、MDで表示してみた。まだ全く動かず、どのぐらいの大きさになるのかイメージを取りたくて。
https://i.imgur.com/RLvgcEO.png

スプライト自体は32x32を6枚で64x96。画面に映すまでは大きすぎかな?とは思ったけど案外行けそうなサイズだった。
多分フラッシュゲームなんかではよくあるRUN系?と言うのかなあんな感じのゲームを作ってみようかなと。

元ネタです。
http://www.maroon.dti.ne.jp/pata2-magic/index.html