First, welcome! Second, wow, sounds ambitious.
The biggest problem I see is in actually getting the various heights to "read" as such to the viewer. There are a couple of tricks that might work: 1) Convey distance through scaling: You might try making the buildings slightly smaller scale as you go down the levels. This might be hard because it'll be hard to tell whether the buildings are just smaller because they're not as large or if they only appear smaller because they're further away. You might need to include common elements (shingles, wells, trees, etc.) that the viewer knows are actually the same size but just appear smaller because they're on a lower level. 2) Convey distance through atmospheric perspective: Over distance, colors of objects become less saturated and wash towards the color of the intervening atmosphere. Usually this happens over a very long distance (i.e. between you and some distant mountains) but it might happen over a shorter range in a "thicker" atmosphere...such as you'd get around a bunch of waterfalls spewing water vapor into the air.
That brings up another idea. The waterfalls and bridges are your opportunities to show the relationships between the levels. A waterfall might start at the top and then fall all the way to the ground level...that gives you a chance to use some actual perspective to show distance. If I see a short waterfall and a long waterfall I can guess that the short one probably ends sooner than a long one. And, if I follow the course of the stream, through a waterfall, through a stream on another level, through another waterfall, and through a stream on a yet lower level, then my brain can establish a relationship between the three levels crossed by that stream. That make any sense? Same thing with bridges, but less so...you might have an opportunity to have a bridge cross between two areas at the same level, showing the level underneath it, establishing distance. You'll want some scaling and atmospherics in there so that it doesn't blend with what's underneath, though.
There's another guy on here with a map that has similar issues. He used fading line-weight to indicate atmospheric perspective. Combined with coloring that might be pretty effective. [edit: here's the link]
Hope any of this helps...and I'm sure some of the others will have some ideas for you. Good luck with it. A city map's ambitious enough without all of these complications!