Create an Interactive Map
That is, more interactivity than picking up the usual map and following directions calls for. There should be a lot of 'back and forth' between the map and the reader. Either one shouldn't be able to get from point A to point B just by the geographry of the map alone, or the map should serve some interactive function besides that of a map.
A treasure map with detailed instructions
A navigational sea chart that requires checking one's bearings to reach the intended destination
An interactive map in flash with locations that can be explored
A map one can eat, wear, or play
A map that the reader traces a route by following along in a companion guide [Technically, a google map + direction set would fit this, but I am thinking more along the lines of Futterer's maps that one uses Bible chapters to make sense of his journeys - his maps would be unintelligible without the ability to follow along].
A coded map that needs a key or marker to reveal its true nature
A 'randomized map' (such as a set of tiles) that makes a new location every time based off how they are laid out
And so forth.