I suggest a thief.
You could use a Red Mage, which would be incredibly useful in the beginning. But after class change, the specialization required in the later dungeons only leaves the Red Mage wanting.
The Thief, on the other hand, is not really useful in the beginning, but becomes incredibly useful after class change. The Thief can run very well, and can sometimes match the Fighter's damage dealing when properly equipped. And after class change, the Ninja will be very powerful, essentially acting as a kind of Fighter himself. Like, having a Fighter after class change, not as powerful as a Knight, but still very good. And he can also use low level black magic. You just need to keep the Thief alive in the meantime, and he will become a great asset.