I think it would be a great feature to add in a future patch or expansion the ability to place your palace at the start of the game before anything else happens.

Essentially, when creating a random map, you can select the option of "We just got here" or something to that effect which means the palace hasn't been built yet (this option reduces the difficulty rating). Then, when the map loads, everything is there as it normally would be, except there's no Palace. The game is paused and the only thing you can do is place the Palace where you desire, where upon it is built instantly and for free. The game will not un-pause until you place the palace.

This gives players a bit more flexibility in how they play by positioning the capital. Suppose you want to play an oil baron, but have the dumb luck of starting on the opposite side of the map from an oil well. This option would alleviate that annoyance, while for those who prefer the challenge of a random start location, don't tick the option.

I want this.

So also the first teamster- and housebuilder-office as long as the farm has to be placed... and also some roads. Without those the city would die immediately.

To much in my mind.

Indeed, it would be lovely, but also for the Dock, which are the two irreplaceable buildings: Palace and Dock.

The rest (roads, farms, teamsters, construction office) you can replace one at a time by building a new one before destroying the old.

Some times I ditch a random map just because the docks/palace aren't sufficiently well placed in my opinion.