I glanced through the map editor and see two ways of "introducing randomness" (please correct me if I'm wrong E. Albright or anyone else):
Editing out and editing in refers to disallowing a site as a starting site with random, and allowing a site as a starting site with fixed. Unless we're desperate for start sites, the map is unlikely to see any other alteration.
On retrospect...map editing will require editing the map file and using the ingame editing (mainly for convenience). The question is whether to select predetermined start sites and edit in eligible sites, or not select predetermined start sites and edit out bad start sites. It'll basically come down to two things:
Which list (bad start site or good start site) is longer, and
Which list is produced more or less first?
Also, if someone is going to edit the map, one idea I'll mention is the removal of the worldwrap. While it will lead to cornering and other bad things, it just seems more authentic to the area. You can't go south of Alaska and get back to Alaska without hitting the South Pole (not shown). There is no land bridge between North America (mostly missing, but Alaska is part of it) and Europe (not shown), except the Bering Strait. It seems more accurate to me to assume that the nations can only get from one land mass to the other by the Bering Strait, or water travel.
Because of the balance problems removing the worldmap would produce, editing in good start sites is more likely.