In any game, information = advantage. Card players know this well. As such, the less random you make the game startup, the more advantage you have over the AI.
It is my opinion that a difficulty level is not truly 'mastered' unless the player can win almost all the time under completely random conditions:
Random world size
Random world type (shuffle map or a mod random map script)
Random leader
Random personalities
Random barbs
Random climate
Random shoreline
The more settings the player picks, the more he/she is stacking the game in his/her favor since that player enters the game knowing some of the parameters.
with Random Barbs, you might have raging, you might not, so you truly have to make a choice whether or not to prioritize the Great Wall. If you intentionally set Raging Barbs, you know the Great Wall has a high value and should be prioritized in most cases.
Everyone should play however he/she likes, and I have no problem with that. What annoys me is when people come on these forums and brag about how great they are at some high difficulty level but then you find out that person always customizes the game to his/her favorite settings, favorite leader, favorite traits, and regenerates the map until getting a favorable starting position. Yeah, I could win every hand of poker if I hand pick my opponents, the seating order, and reshuffle my hand until I have four aces.
As such, my opinion on regenerating the map: each regeneration is a game loss and should be counted as such if Civ4 tracked win/loss statistics.