Around the time you get the ice digger, there'll be one new character to pick up (and an old one to get rid of) as well as three optional dungeons to explore before. Most walkthroughs here simply do things in the order you come across them. So that would be Myst Vale/Climatrol/Meese/Weapon Plant. Some people dig Raja and dislike Kyra, so they like to keep the green ol' wisecracker with them as long as possible while others (like myself) pick up Kyra as soon as possible before doing any dungeon hopping.
So what's your order usually?
1) Myst Vale/Climatrol/Meese/Weapon Plant ('cause that's the order it's probably "meant" to be played)
2) Myst Vale/Climatrol/Weapon Plant/Meese ('cause you like your walking wisecracking inn)
3) Meese/Myst Vale/Climatrol/Weapon Plant ('cause Kyra needs love too. And experience)
The reason I usually do the third one is because Kyra needs all the experience she can get before you start exploring the Air Castle and Garuberk Tower, both large dungeons with lots of tough encounters and nasty bosses at the end.
Even after Raja falls ill, he continues earning experience points in the background and his level curve is very slow to begin with, so he doesn't really benefit from additional experience at that point.
Kyra, on the other hand, needs several levels in order to gain stuff like Warla, NaFoi and NaRes and doesn't start earning experience until you pick her up, so it makes sense to make her part of your active party as soon as possible. Not to mention the fact that against the biomonsters inside Myst Vale and the robots inside Climatrol, Raja's stuff like Holyword and Saint Fire is useless anyway and as far as out-of-battle healing goes, Kyra isn't much worse than Raja.
I never have an issue with learning Warla before any of the boss fights, and I usually roll with Gifoi since she never learns Nafoi before PD2, never had any problems, really. Maybe it's just me, though; I mean, when not using Gifoi in the boss battles, she's usually healing, so I guess I don't see the need to force her into the party any earlier...
On the other hand, my last playthrough I forgot to go to Climate Control before going to Meese, but I didn't notice a particularly higher number of levels that Kyra earned, so maybe I'm just rolling with a lower level in general?
As much as Erpy's idea about ideal experience for both Kyra and Raja makes sense to me, I usually just do them in the order I run into them. I guess that's number one. I don't see any reason not to do Mystvale as soon as I get the Ice Digger. It's very quick and very useful.
Either 1 or 4, personally. Myst Vale is quick and close to Tyler, so I sometimes go there first, but I'll definitely trade Raja for Kyra fast to make those two big midgame dungeons a bit easier (also I found Meese before Climatrol first playthrough, might just be me...). I also think Kyra is probably more useful than Raja in those mechanical dungeons anyway - both have enough reserve healing to make that not an issue (not to mention neither dungeon is long), but Kyra's speed and offence make her more useful at getting through random battles themselves.
The RPG Duelling League: www.rpgdl.com An unparalleled source for RPG information and discussion