Just make it like the one in ff6 (3) - have a black screen (20x15 would be nice; I don't think scrolling would be good) with a temporary character (or storyline charactar that hasn't been seen yet, like Mog) and three (or however many) different parties. When you talk to someone in the parties, change the party by adding those characters and removing the temporary character. Then, teleport to the area where the scenario starts.
Be sure to turn on a switch at this point so next time you go to the black screen, you can't choose that scenario again. And, after all scenarios are done, turn on a switch for the next time you go to the black screen to teleport you to the area that your characters meet (like Narshe).