Google Maps and the like have all but superseded paper maps. There are certainly clear advantages to having a map that can dynamically plot your route, give you turn-by-turn directions, show you realtime traffic patterns, overlay satellite images, or point you to the closest public toilet. On the other hand paper maps excel in some other really important ways too. First, they're easy to annotate. Second, because they're usually printed in a large-format, it's no problem to simultaneously assess both the big picture of your route (or the map as a whole) as well as the details. You just don't get the same effect by zooming in and out of a Google map, especially on the small screen of a mobile phone.
These two characteristics of paper maps, in particular, have not yet been successfully replicated in electronic maps. So how can we rectify that? In terms of annotation, I think we could integrate rudimentary drawing modules into maps--modules that let you create layers of annotations "above" the map itself. You would be able to draw routes, mark points of interest, write text, etc. right on the map. You should also be able to create an arbitrary number of layers, order them and show/hide them at will (like Photoshop).
As for the fact that it's difficult to see the big picture on electronic maps, perhaps the solution entails creating some smart animation functionality. I'm thinking something similar to the fly-to feature in Google Earth. Plain old Google Maps (or other electronic maps) should let you do a fly-over or driver's-eye view traversal of your route. Another nice feature might be a preview of the next turn at the driver's-eye view. What would be really cool is if this also displayed landmarks along the way so that when I actually drove the route I would recognize it and not miss the turn.
I'll be the first to admit that I'm not really up on the latest in GPS mapping technology, so if all this already exists, let me know. If not, I think the next generation of mapping technology would be wise to support these features.