I watched the Lord of the Rings again with family over the weekend. And when Strider points out Amon Sûl, something struck me. An icon on a map isn't going to give players as evocative of sense of that place as an actual image. And I thought of Victorian illustrated texts with their illustrations framed in circles and rectangles that nestle right into the text. Why not do that for a player map?
The inset pics would need to be things that were fairly common knowledge to the surrounding communities. Essentially, the pics are a stand in for the rumors, descriptions, and lore people tell the players about locations. If players are exploring new territories, and you feel up to it as a DM, you could add insets as players pass close enough to featured locations.
Update: I played around with the idea a little more. Imagine these insets bordering the whole map, those near the starting point of the campaign filled in, those farther away unknown. But, you know something is there. You could give players XP for every Wonder of your campaign world they uncover.