That would be the easy route but no real fair to humans.

Well, sometimes fair isn't the point.  We humans have advantages that you can't easily program into the AI.  As you said -

Anything you come up with will be a cheat to some degree.  You just have to give the AI a little penalty for using it.

I don't get why pioneer pathfinding is that CPU extensive either. Shouldn't it be quite simple to mark tiles that have a threat as no-go and then do a simple adjacency matrix power calculation weighted with movement costs for the shortest path without threats? In general you shouldn't move settlers by themselves that many tiles into the wild, so the matrices shouldn't grow that big before you need to have an escort and thus solving the problem.

When I play Civ, I don't use an unescorted settler to settle more than, say, 20 tiles from my nearest city. If I need to go further than that, I always get an escort that then starts guarding the city.

Since you can do the calculations on the human turn and the computer players probably won't have pioneers scrambling around constantly, there shouldn't be that much trouble calculating the paths. Then again I don't know how little resources you have for one task such as this when calculating the turns in parallel.

This is another area where you're at an unfair disadvantage.

A human player will leave them unescorted, and reload if they're eaten.  It's just human nature: AI's have more fun losing then humans. 

One turn at a time and recalculating is probably the best chance, followed by giving pioneers good sight radius.  Pioneers are largely early game units, so AI times won't be that long in the start of a game.

That Pioneer death= respawns after a few turns idea is great though, and might be the best solution.  This would also keep humans from saving/reloading, and not cripple an AI in games where it loses and the player doesn't. 

I also like the pick a square, and have the town form a few turns later.  If the town is attacked while forming, it disappears, and monsters can attack, but the unit doesn't have to physically travel there.  You'd probably use your scout as a garrison until the town is formed.

Are either of those last two ideas viable on the game design front?  They sound really neat.

Here's an idea that would help the issue a little bit: make the settler unit a decent defensive unit that cannot attack or be grouped with anything else. Kind of like the mobile outposts in RTS games (command & conquer etc). Since a settler founds a whole town, it makes pretty good sense for it to have enough firepower to fight off a few bandits or the occasional beast, but not anything stronger like dragons or skags. It also makes sense for the settlers to not be able to pair up with anything else, since it's a convoy with loads of stuff to found a city and as such is too big a group to fit into an army. It automatically fills up whatever logistics quota you have for that unit.

This would pave way for an interesting addition to the Logistics tech: the better your logistics is, the better defended your settler units are automatically. However add some small penalty to the new city if the settler unit was damaged before founding the city. Perhaps 1-3 turns of no production in the new found city while they repair the damage.

Wouldn't call myself a coding expert in any way shape of form but I'll take a shot at why this is so CPU intensive.

If all you want to do is find the shortest path from point A to point B for a unit, that is a fairly easy computational problem. The simplest implementation of Dijkstra's alogrithim (well known shortest path algorithm) operates in O(V^2) time (V is the number of vertices). Basically the time it takes to find a solution is proportional to the number of vertices squared. For instance if you were trying to figure out the shortest route that a truck could take between two towns, and had a map with a bunch of towns in between and knew the distances between all of them, you could find the optimal answer in some time that was proportional to the number of towns on the map squared. The problem you describe is similar to this, the paths just get different weightings based upon static threats that exist on the map. Instead of finding the shortest path you're finding the least dangerous and shortest path. The problem gets a little more complex, but its the same order of magnitude. In the grand scheme of things an algorithm like this that can operate in polynomial time is pretty fast.

The problem Brad is trying to tackle is on a very different level of complexity. You are now not just tying to find the shortest path between two points for a unit. You're trying to find the shortest path while also taking into account the possible actions of a number of other entities that can also move on the same map that you have to either avoid or counter in some way. The threats are no longer static constants, but rather other actors that are solving their own little constrained optimization problems. I can't just find the shortest/least dangerous path assuming that the threats all stay in the same place. I have to find the shortest/least dangerous path assuming the threats will make a counter move to every move that I make. Don't know for certain, but I imagine the time this takes rapidly blows up to exponential or even factorial time calculation. 

But pathfinding shouldn't be that hard, even with moving threats. You have your basic grid, and you can just block out any tile as inaccessible if it has a monster within 1 tile (so a monster creates a 3x3 dead-loss). Add in wildlands and borders to factions that you are neutral or at war with.

My point is, even moving enemies should have very little impact on how you proceed. You just have to avoid them, which isn't very difficult.

Would the easy way be to leave the AI dumb and just reduce the "threat radius" if there is such a thing for caravans?

and if there isn't such a mechanic it should be added. Large armies should scare away small groups of wild monsters and small armies should look like prey.

I'd be interested to know the exact problem that you're trying to solve. I'm sure you're aware of the solutions posted in this thread, since they're the solutions that are used in nearly every tile-based game.

There are lot of obvious solutions to these problems.

FE is quite a bit different than other tile based games in that the world is really REALLY dangerous. It's not like Civ or WOM or what have you where there's an occasional threat. It's more like an obstacle course of threats. The world is out to kill you hard.

And since I write the monster AI too, I am doing my best to make sure they're really good at killing stuff (without them being too unrealistic -- they won't chase you across the world or anything, they don't care about you that much).

Finding a delicate balance between caution and reckless is a non-trivial programming exercise.   If you ever watch champion strategy gamers (like Starcraft) you'll find that the bold win more often than the careful.

I agree.  If the world is an obstacle course of threats, the only decent way to get the pioneer through is by having a sufficient escort.

Flying units would be a good solution.