I too would recommend reducing the size of both the province and capital labels, and their corresponding icons. In addition you might play around with: lowering the opacity of the regional names (I'd start at 50% and go from there); instead of curving the provincial labels try instead making them straight but in all caps (all of the curved text tends to detract from the clarity of the map); as you suggested, try out using different colors to distinguish the provincial labels from the city/capitals. Another thing you could try to attempt to save space is reduce the size of the regional labels as well, but make them in all caps and widen the space between each of the characters/letters in the labels.

Cheers,
-Arsheesh