I think this is a good discussion, and I am glad that we are having it. (And actually, it really does more appropriately belong in this Discussion thread, rather than in the survey/data-collection thread, that I started.) Also, I don't really think that we are all that far apart ...
I believe that most 4X game players want variety in the games they play. They want meaningful choices; they would like multiple paths to victory; they appreciate customization; and they appreciate features that foster Replayability. I may have overstated the point I was trying to make, by using the term: optimal strategy. I probably should have talked more about viable alternative strategies . For my part, I just don't want to see all our games, at all levels, and with different Sovereigns/races, always start with the same uniform starting positions. I want to preserve some measure of variety. In Chess I expect equal/uniform starting positions; in monopoly I probably want them; but in Civ 4 and E:FE I (personally) don't really want that ...
But most of those new players WON’T be rerolling until they find a good starting location, and will just put up with what they get the first few times round. As an advantage it’s one that only applies to experienced players and 4x veterans. If anything it puts new players at a disadvantage.
I think we may have an honest disagreement on your point above. I don't want the [ctrl] [ n ] feature to be a secret! I certainly want the newest novice players to be aware of that feature. But assuming they are, I woud fully expect them to play around with it, experiment with it, and seek to use it as one of their first meaningful choices ...
Now, I do like your suggestion, that starting locations can have some variety, within a context of some balance. In other words, we don't always have to have all players (human and AI) start the game sitting on a 4/4, with one mana shard and one iron-pit close by. We could have one starting position which has horses, iron, and grain nearby; while another has 2 crystal shards and gold nearby; and a third has an apiary, wargs, and a mud-pit nearby; etc. And some of these can have a 5/3, or a 5/2, or a 3/5 (are there any of those ?), rather than a consistantly uniform 4/4.
Actually, Aerion Istari's suggestion may be the best compromise. Have a selectable switch that offers either "pre-balanced starting locations", or "not-so-balanced starting locations". Given the option, I would probably go for the second choice 90% of the time ... but other players might not ...