Lore cards
Take a page from Dragon Age's Codex and have a system for Lore and flavor text. This would help make the map less generic and give more of a RPG feel. The Card-based way information is already in the game is nicely suited for something like this. Ideally this would be for a pre-designed world map but could be adapted to randomly generated maps.
Three possibilities for such a system in terms of complexity:
1. For history and lore only - Cards that describe places of interest or important mountains and forests - Forest of Balint, Plains of the Old Ones. Can include ancient history text similar to the way Dragon Age adds text about old wars and the relationships between realms like Tevinter, Orlais and Federen. When entering 'enemy' territory, could have a change in the texts to emphasize the evil there, e.g. Circle of Human Sacrifice. Interesting text for dungeons, ruins, temples.
2. Integrated into the quest system - Have clues in the flavor text to lead to quest starting points. Have cards for objects of interest like burning caravans (quest for bandit removal, for example) or graveyards.
3. Meta-game - Collect all five cards for visiting five named grandmaster leatherworkers and gain 'Inlaid' leather armor tech or have a Risk-style turn in system (pairs or triples of similar cards for gold and resources).
Ex. Collect cards for 'Friendship of the Lizard folk' and complete for a certain number of special units.
There could be minor rewards for obtaining part of a set at 3 of 7 and 6 of 7 for example.
A very flexible system could get quite involved. For example, only 4 of 12 places of interest are on the map initially. 4 get revealed if the inital 4 are visited. 3 are 'invisible' and can be figured out from the 2nd tier texts. The last needs you to find a map first.
Such a system would be useful for modders who might want to create highly tailored worlds with background text.