Hey - cool idea! I've been seeing a lot of "serious" stuff, and it's great to see something this "out there". I like you're ideas - flying sharks are a great idea ^_^ I'd love to help out in any way I can, but a couple questions:
1) what style are you looking for? Smooth/clean vector? Sepia-tones? Old-style? Hand-drawn? 3D? Maybe post an example map in the style(s) you're interested in.
2) do you want sketches of the different encounter types shown on the map?
3) do you have names for this stuff already, or do you mind if I throw a couple on there?
4) how "serious" is this is? Are you looking to do something in the line of Conan, or more like Terry Pratchett? That can affect the names (the difference between Draggydska and DragonSpike, I guess)
Sounds like this could be really interesting! Oh, you said "D&D-like" - what system are you using? Or are you designing it?
So many questions! But I hope I can help!