Well I wouldn't mind a Fog of War of a fairly basic sort. IMHO a weakness in the game at the moment is that it's a little tedious moving around the map, dodging Dark Knights notwithstanding. That'd be improved if there was more to see and perhaps do while you're traveling, but it'd also be improved, at least at first, by adding a feeling of mystery and exploration to travel.
I wouldn't have a black or severe looking FOW, I'd just take all the cities, salt mines, bandit lairs and the like off the map until you discovered them. Instead you'd just see the natural geography of the land, and if you needed directions you'd be able to get them from merchants, wandering peasants and the like.
Anyway, it might be too much effort for too little result but I get the feeling a bit of initial exploration would improve people's first impressions of the game.