With an emphasis being more on nations and their borders I would suggest an antique/Mercator style with very simple terrain...probably symbols or brushes. You can try the shaded relief method for something quasi realistic if you want.