While I agree that adding the cardinal directions to the map would be handy, I have to take exception to your example. In game, I tend to think in terms of left, right, in front, behind, etc.. When someone tells me come south and you'll find us, I have to stop and think about it.
And just as a frame of reference, I completed a 4hr land navigation course in less than 1hr when I was in the military, so I do kind of know my way around a map..
In other news, the lack of in-cave maps and all maps being single-tiered has been a sore point for me since I started playing 2 years ago. As has been mentioned by others, I really liked the way that GuildWars implemented their maps - although I guess they never had to deal with multi-level maps.