To me a map needs a fair few things to actually be 'good' and many may already have been listed but:
* Use of appropriate background music to set an atmosphere (a jaunty tune for an happy little village, or a gloomy track for a dark and dingy swamp) a wrong track can ruin a map for me to be honest.
* Use of sound effects for various things (water falls, rivers and sea aren't silent, so add SEs)
** Further to the above, progressive SEs are awesome but time consuming, as you move towards a waterfall, the noise gets louder etc.
* Future Areas (caves that you can see but can't enter (you need a key or weapon etc to get in)) to make people remember the area to come back - it also leaves people curios to what's actually there
* General Layout - none symmetry in forests, trees don't always grow in lines, put a lot of variation in the maps, flowers and such, but dont clutter it so much that it feels more like a picture than a place you can explore.
* Multiple elevations if you have mountains make them feel like they are above the player (this requires placement of trees and such to help make it feel more elevated)
* Out of the way areas, give people rewards for exploring places that aren't the way you are supposed to go.
* Continuity - if you have the bottom half of a tree on a south map, if you enter the north map the other half of the tree is shown, I like this as it feels like you aren't skipping random parts of the map.
EDIT:
* NPCS having an NPC walk round that says "hello" from 100 different 'fillers' is quite tiring and makes the game feel very bland.
** Create conditional branches for various chat lines and information about the area
*** Make NPCS chat change as events in the game unfold----
for instance
A little village has just heard news of another village close by being raided, there normal HEY chat and general chat can be more concerned about others, this can be done with simple event switches as well.
^this makes it feel like your world is a world, as others react to events, rather than them only being felt in one town.
**** you can also have certain npcs give potions or gold after you've done a main quest if you speak to them "I Heard you helped out such and such, I dont have much but take this to help you on your journey".
Again its more reactive to events in the game!
(I can provide screenshots of examples of what I mean if anyone finds this useful but my explanations are a tad uninformative

)