The game does not seem sure if it is sand box or linear. It plays very sand box except where it suddenly does't and sometimes the sand box element doesn't seem to work that well.
Example: I hit Keara's FF first (simply 'cos it was marked on the map which I took as some sort of hint) at level 25 i think. I had a week's worth of hard and exiting fighting there, it was the highlight of my game, epic, and i was getting 2300 XP per kill to start so I advanced I think from 25 to 31 in that one extended battle.
However once I'd done that all the other FF, invaded Broken Valley, everywhere became very easy and a bit boring. I was getting only about 80-130 XP per kill which at that level hardly touches the sides.
There is definitely a minor issue with Orobas Fjords in that inevitably you will over-level if you try and do everything. Still though, doing everything should put you at about level 35, which is the level of the lowest enemies in Flames of Vengeance.
Flying Fortresses are really dangerous to enter before the mid-twenties, but clearing your first one will almost certainly give you a whole bunch of levels. Doing Stone's (the "easiest") at level 26 took me to level 30.
