A few suggestions you might consider:

Include a custom frame, compass rose, and set of icons for the map. Making all of these elements thematic to your subject could help.
Use a font that's clear, but suggestive of the setting. For the fantasy maps I do, I'm fond of Kingthings Calligraphica, available at https://www.fontsquirrel.com/fonts/k...-calligraphica
Use color.
If the map includes water, consider depicting bathymetry.