No doubt a game in the Langrisser/Warsong series. Then again, it doesn't really fit the description, because in Warsong it's the main character - who lacks a horse - and old guy, aswell as a bunch of NPCs. I don't think you get the weak wand girl until a bit later. And in Langrisser it's basically the same, only blue-haired warlock guy instead of old guy.
Still has to be that series. Seems familiar?:
Edit: Oh, and IIRC the main character is red-haired in both Warsong (genesis) and Der Langrisser (SNES). Could be brownish though, it's been a while. Warsong was released in English, and Der Langrisser has been fan-translated. The rest of the series is asian only, unless someone's been doing something good since I last checked (admittedly ages ago).