Surprised no one mentioned this, but the actual granddaddy of the "play the heroes' scenarios before they team up" RPG is Dragon Quest IV. It doesn't have the visuals of later such games, but it is still fun if you like that kind of gameplay. I suggest playing the DS remake since it expands the story and has a 2.5D presentation. (There's also DQ V & VI on the DS with the same style, but with more conventional DQ progression.)
Speaking of which, Dragon Quest III HD is out now, and it has the same kind of graphics as Octopath, though a bit more Akira Toriyama-esque. It is likely the best version of the game, as the rule for this series is that whatever the latest remake is will be the definitive version until they make the next one (for the record, this is the 6th DQIII remake).