Dragon Quest III (Famicom)
I completed this just now.
Besides the Hero, I went with two Martial Artists and a Priest, and I had a blast with this party. The two Martial Artists started out pretty weak, but became extremely powerful during the middle and endgame (it was also nice to not have to spend any gold on them after the first few hours). I ended up completing the game at levels 38-41 depending on the character, with no need to grind for EXP or gold at all.
It starts out very linear, but opens up only after a few hours, and you're free to explore, gather information and clues, and solve the main quest of finding the orbs mostly in any order. The game of course becomes linear again toward the end.
One great thing about this game is that it does very little to "gate" your progress once the world opens up, as there are very few "boss" characters throughout the game.
I love the fact that low-level spells are effective even against endgame enemies. I got a ton of use out of the spells that cause sleep and silence, and even the spells that banish or kill enemies. It was actually pretty fun to figure out which enemies are susceptible to which spells. Combined with a very reliable run command, you have several tools to disable or avoid tough encounters.
Anyway, it was an amazing game all the way through. It basically does everything DQII does, but even better (with the exception imo of the soundtrack).