I'd vote for another map - anything with fixed starts. Random starts may result in very odd (and bad) capital placement for some nations.
In order to be constructive, I digged in llamaserver's map listing, seeking for 9 land, 1 sea maps with fixed starts.
And here is what I found:
http://imgur.com/qmvmq
Map's thread
http://forum.shrapnelgames.com/showthread.php?t=44078
Comments from discussion: "This is a tournament quality map that will be added to my long list of favorite maps. The idea of having impassable mountains with caves that connect opposing nations is always cool. Every aspect is balanced and well defined. The colors add to defining the territories."
Download link:
http://forum.shrapnelgames.com/showpost.php?p=772280
Map's placement on llamaserver is highlighted at
http://imgur.com/qmvmq