Imho, political borders (even if you don't go stricly with the same ones as in the example linked), ways of transportations, maybe designing some "pre-modern" symbols and the way you're going to label it would probably be the things that visually give the visual touch you're looking for.