Over at Axis maps they posted an animation of a paper map they were asked to do.
The animation shows the map in progress, each step of picking the right font, color for the water etc. It's a nice reminder of how much better maps can be made by the application of time and expertise.
Paper Supported by Google Earth: The map was for a group of hotels and was designed to be printed. I'm fully in favor of still using paper maps in these sorts of situations but I wondered if instead of just giving guest the map you could produce an animation of the layers of the map in a Google Earth tour. So you would first fly the guest into the area then reveal placemarks of important points one by one with labels. This would be shown on a video loop in the foyer and could be used to help guests see what they can do with the paper map and what is in the vicinity of the hotel.