There's not really a good point in the early WoR to level up. Not until after you get the airship, anyway, or at least once you get past Figaro. I'd say, anticipate the WoR being harder, and level up accordingly before you get to that point, if you think you need to. I think the Floating Continent is the best place in the game to level up ... still a challenge, but you get a lot for it. And the battles in FFVI are fun enough to go through a lot of 'em just to level up, anyway. It ain't like it's tedius or anything.

And the levels of the characters you get them back depend on the levels of YOUR characters at that time. Like, say, if Shadow is level 30 when you leave the Floating Continent, and you get everybody to level 80 before you get him back, he'll be somewhere around level 80. Keep that in mind, since you already know the first characters you'll be getting back. I you level up just ONE character, and it's the one you start out with in the WoR, then all of your other characters will be at higher levels when you find them, too.