It's good to see this conversation is being revived since (at least according to the latest game I've played of Beta 4) pioneer spam is still problematic.
In the game I just played I had to effectively outpost and found cities over my area that I wouldn't have normally done to block off other computer players that were sending in pioneers and refusing to talk to me when I went to demand that they remove them. As the OP originally stated, it does reduce the immersion and changes the narrative of the game quite a bit.
I'm not sure what the solution to it is, but I think at some point, mediocre settlements need to punish the player. Right now there is no downside to players plopping down a settlement any spot they see. The growth hit alone is not enough to discourage the activity, it is easy enough to buff up growth via spell, building, consulate outposts, etc, to not make it a significant detraction from a player making that "choice."
My solution: tie number of settlements to a fixed amount. I'd suggest limiting the number of players settlements to their faction prestige. It actually already looks like it scales quite well with game pacing (albeit I anecdotally looked at it for one game) so this would require little rebalancing of the prestige mechanic to be effective. It also forces players that want to expand fast to forgo magic and warfare research in favor of civilization for the prestige boost. That makes it a strategy with risks (fast expansion with weak troops to defend it) and potential rewards (potential late game juggernaut once the settlements get developed). Additionally, this idea fits with game play, if you have a less prestigious faction, chances are it's going to be hard to convince settlers to found a city in the big bad wastes.
I don't think penalizing the player for wanting to make cities is the right way to go about it. Already, city growth is averaged across the entiraty of the kingdom, limited by its presteige. Having further limitations would remove the desire to build a multi-city archetype.
In my experiance, the more memorable TBS games I ever recall playing involved 5-10 cities. Not too much that the management becomes overbearly, yet enough that you always feel you have something else to do. I can see with FE, and in inclusion of heros, that 10 cities may be too many as you may have too much to do. However, 4-7 should be obtainable.
Now that said, I don't think it should be EASILY obtainable. I really like the concept of 'cataclysm' where most of the landscape is ravaged. A player should be willing and eager to build settlements whereever possible in order to struggle and rebuild your once powerful civilization. Sometimes a good plot of land is guarded by a monster that you have to defeat. Other times, you have to deal with the warping of the land (like with the wildlands). I think there should be other times too where technology and/or magical spells should enable you to build in some locations that normally weren't open to you at the beginning of the game.
In the end, the current game I'm playing (see game 4 of my thread) has just founded it's 8th city and it's BY FAR the most enjoyable game yet (of the 4 I've played)
. In fact, the most frustrating part of the game is that the cities aren't leveling fast enough because the growth is spread out. Completely against the feel of the game, imo, cause I'm suceeding to rebuild my lost empire and I'm being punished for it. I would figure that, out of the ashes of a cataclymic world, people would flock to the banner of the hero who is bringing order to chaos. (and that said, I feel that the utopia that was given me at this start was quite a fluke and well beyond the normal expections of the starting locations...)
Anyways, just my view...