I actually don't get your problems. I play with two melee fighters (both without Pawn talent) and I rarely have any distance problems. They could use one additional AP, sure, but then again it's not that bad the way it is.
Likewise, with the Red Prince and Ifan as my melee characters, I haven't found their mobility to be a serious hindrance. My issue is with enemies that attack five times in one turn.
