The best way that I've seen to handle this is to draw the map in chunks. Before the session, draw the first several rooms of the crawl, either as part of your pre-game prep or as people are coming in and getting set up.
If you have a break in your session (say, to order pizza), spend some time during that break erasing the map and drawing out a new set of chunks based on the players' location.
Most of the time the layout of the map isn't actually important (since the PCs can only really see the shape of the room). If it is important, just cover the map with paper, and remove sections that covered areas explored by the PCs.
You can also print a copy of the map without details on it, and hand that to a PC. Have them draw the map as you're doing the initial narrative.
This will work well for tactical games, like D&D 3 or 4, where the players move through the dungeon relatively slowly (room to room). For games where the players might fly through rooms quickly, use a small-scale map for the overall dungeon layout, and use the battle mat for the rooms where the fighting actually takes place.
First and most important point: The actual map is actually the least important and interesting part of a treasure map. Remember, the purpose of a treasure map is almost never to make it easy to find a treasure - It's to make it easy for the mapmaker to find the treasure - or possibly one of his relatives, if he doesn't manage it himself. As a result, most treasure maps are deliberately made obscure, misleading, and cryptic. So, to turn that around, the important parts of a treasure map are the clues that let you find the treasure, and the obstacles that make those clues hard to understand; These are what makes a treasure map interesting.
Before that, though, a map should include some trick that ensures that only certain people can even start to understand the map. In the game fiction, this is a way for the mapmaker to ensure that no-one but him (and maybe his descendants and friends) can find his treasure easily; From a narrative perspective, it can provide a dramatic way of introducing the map as a recurring theme in the story; And to a GM, it offers an excellent 'early puzzle encounter' and a chance to introduce backstory related to the map. Typical 'map keys' include: a pendant with a particular design that needs to be placed over the compass rosette, the figurehead of the mapmaker's lost ship, or the blood of one of the mapmaker's descendants. For bonus points, design your map in such a way that it doesn't even appear to be a treasure map until the key is applied. (Note that your player characters will probably learn the map-key without much difficulty, or the adventure won't go anywhere quickly; The really interesting question to ask is "who else worked it out at around the same time?" Treasure map adventures are often races.)
Solving that first puzzle doesn't mean your treasure-hunters are home free, however. The initial hurdle is just that: The first of several. Treasure maps rarely have an 'X' marking the spot - of if they do, 'the spot' will be a trap, trick or warning for would-be treasure hunters, instead of anything useful. (A hole in the ground to make it look like someone else already found the treasure is easy to set up).
Instead, the map should contain clues designed to let treasure hunters navigate by means of landmarks. Often these clues will be written as a series of cryptic riddles that can only be solved when at the location the previous riddle described; In other cases, the directions will be straightforward, but the landmarks themselves will contain riddles or clues that can only be understood in combination with information revealed by riddles on the map. In either case, it's shouldn't be possible to find the treasure with just the found clues or map alone.
So, getting back to your question about how to make each piece of a multi-part treasure map interesting, each piece of the map needs to be pursue-able on its own. Not all the way to the treasure, of course, but each piece should be able to get you a vital clue without needing the others. Fortunately, there's a lot of precedent for this, especially with maps divided into sections to prevent the treasure-hiders from betraying each other: Thus, the riddles and clues the players find need not lead from one to the next in a linear fashion; Paths can branch and merge, and in some cases, the answers to a series of puzzles and riddles might be combine to form an additional, final puzzle. Again, these puzzles will be designed to be solved by the mapmakers-and-their-descendants, and not outsiders; Having access to a journal or biography of the mapmaker can be a big help. For a GM, this is your big chance to establish the personality of the map-maker through the kind of obstacles and puzzles they design; Remember, not all charismatic NPCs need to appear 'On Stage.'
If you're looking for more specific ideas, I remember once following a treasure map where each clue indicated a location in sequence; Then, by 'joining the dots' on the map in the order the locations were visited, an 'X' was drawn. In another case, each section of the maps described a set of directions presented without context; Only when all the map was assembled could the correct order of turns be discerned.
Best Answer
Use a Ring Binder and Poly wallets
I once ran a similar scenario, but mine was a dungeon that went down a whole lot with plenty of sub-levels.
For this, you will need two ring binders, a whole bunch of poly wallets, some paper, a pencil, some tape/glue/adhesive and some scissors. Optional extra is some tracing paper.
Draw each discrete room/explorable area separately on paper and cut them out. Make sure they are all to scale with each other, and when fitted together will fit within a poly wallet's surface area
Stick each room in/on a poly wallet, so that when you layer them on top of each other, a full level is formed like a jigsaw
Optionally, add a layer of tracing paper between floors to show the difference in height/depth
Stick them all in your ring binder
As your party explores the dungeon/temple/whatever, take the new room from your binder and place it in the correct position of the party's binder. Thus they will slowly uncover more of the dungeon and be able to see how it all fits together as they go. Because each room is fixed in place, this will let your players flick through the binder and guess where certain stairs will lead, identify gaps for secret rooms, etc.
Note: Unless your dungeon is very tall and thin, this map will not be suitable for miniature combat, but that's when you break out the dry-erase grid and sketch the relevant area.