The mediterranean has the advantage that it creates a lot of geographically separated areas with natural borders. The high frequency of rugged terrain, rivers and mountain passes will give defence a slight advantage. A good way to do it is to place civs in areas where the core is easily defendable and they can fight over open ground which several civs have access to. Here is a quick suggestion of possible starting places. I found 13 logical starts marked with red circles, but was a bit uncertain regarding the 14th. I made 4 different suggestions marked with blue circles.
Note that mountains will be used to create mountain passes, the rivers I have put on the map should be water 1 tile-wide in order to make crossing a difficult process. The occasional wading point would make ships very practical yet not a necessity. Unless a player is truly incompetent then defending his core lands should be reasonably easy. The border provinces however would be easier to lose and gain, hopefully creating a lot of dynamic fighting over overlapping easily conquerable territory, and ensuring that a civ would require considerable effort to wipe out. Regarding your complaints St.Jon:
1. Though some civs are in a corner here they all have at least 2 neighbours that should be able to challenge them. In addition, the ocean rivers as well as the easily sailable mediterranean would allow colonial outposts, sea raids, and expeditionary forces sent to deal with powerful civs at some distance away. The increased ship movement mod may be appropriate.
2. There would be no age of exploration on a flat map, however, there would be possibilities for early to mid game colonization, races to grab various islands, inaccessible or low-value terrain and inland river-coast cities.
Some areas with mostly hills would not likely be settled until at least the advent of Machinery. Other areas could be made near-worthless until the development of civil service, or the discovery of clustered resources that would make for good cities only after the discovery of coal or other tech. A minor mod making Corn discoverable with Astronomy could lead to new races to settle previously infertile lands. These are all ideas and examples.
What advantages are there to this? First of all a pre-made map would be more balanced than a random one. Second of all, I think it would be interesting to play a real location with all the advantages and disadvantages stemming from it. The great thing with the mediterranean is that due to the prevalence of peninsulas and map-edited sailable rivers, no civ has to be stuck on central flat land and forced to fight their way out. Everyone can build a ship, sail down the river and plonk out cities on foreign coasts or undiscovered islands or on some other riverbank.