Actually, I think the answer is a little changed. I've been playing Spiderweb games since Exile II (I did go back and play Exile though!), and I think that this game is just slightly more focused than the Exiles and first Avernums. It's still an open game, but the design has many more hooks in it to lead you in certain directions at certain times.
You start at Fort Avernum, in the Eastern Gallery. Generally you want to radiate out, doing the areas immediately West and North. It's a good idea to hit up Fort Duvno and Silvar to get the various quests, these point you to the "major" starting areas. From there, you work your way west. Cotra and Dranlon have more for you to do and the northern part of the Eastern Gallery has a number of dungeons, in addition to some stuff located beneath the towns. From there, the general pattern is "radiate outward. NE Avernum - Formello, Fort Draco, is easier than the Mertis/The Tower of Magi. In fact, that's when the game really starts to open up. You can start probing the eastern front of the Sith occupied lands (W of Dranlon) and also begin investigating the Great Cave. The Spiral (near Mertis) is tricksy but doable somewhat early. The Ogres just NW of The Tower of Magi are very nasty and probably best skipped the first few times you swing through. The Tower itself is a hugely important place; investigate the first floor but be aware that it's secrets require a much more skilled party. There are a certain, friendly talking species west of Fort Draco with things for you to do as well. That's not too difficult, though the mission they send you on will pit you against some pretty nasty spell casters for the level.
From there you keep pushing west. You can start doing some of the major Slith dungeons, and the important quests in the GC. Pretty soon you'll be exploring the new town, The Abyss, and looking for Ericka Redmark.
Other things equal, I suppose the order would be something like: Fort Avernum, Duvno/Silvar, Cotra, Dranlon, Formello, Draco, GIFTS (I don't think they exist!), Almaria, maybe Mertis at that point. Just doing all the quests you can in each stop, occasionally doubling back. From there you've got a pretty strong base, and exploring strange and exotic locales is a lot safer (though not safe).