Here are some possible start locations. I think it leaves at least 4 provinces between caps. Of course I would take it with a grain of salt since I botched the start locations in Battleground and LDiCesare ended up fixing them.
But I think the idea of leaving the middle area open and starting everyone on the sides is good, either with fixed starts or just setting the middle provinces as no starts. And if we do this there will be no need to change province borders in the middle provinces.