I decided to place the start positions by hand. I'd just like to say it's impossible, so when you end up with a weird start position please bear that in mind!
Actually only one person is starting in a genuinely odd position with only three neighbours, and I'm going to add an iron mine to one of the adjacent provinces to make it better for them.
Edit: Not true in the end, I managed to put everyone in a reasonable spot I think.