I like the direction that this map is going. The more you draw the gameplay to tie into the theme, the stronger that this map will be.
The good stuff:
The 3 (or 2, really) build-a-bonus regions make all areas of the map viable/playable. That's a big help. Keep the bonus for the 2 Pyramids/2 cities/1 of each, and the +1 for 3 towns/tabernacles.
Most of the connections seem pretty clear, as do the killer neutrals (although a symbol for the Red Sea Crossing might help, but that's minor)
I love the weathered parchement look of this map
OK, here's the concerns I have:
Natty has a point- there are a lot of words in the legend with the plagues.
But more than that, I'm not really comfortable with the whole "bonus for plague cities" idea... I understand that ultimately these plagues helped the Israelites leave bondage and begin their journey, but it seems counterintuitive unless you attach the plagues somehow with the Israelites rather than being a stand-alone bonus.
Maybe naming these bonuses could also help, to give an idea of what's supposed to be "happening" when they are held. After all, this map in many ways is telling a story.
For instance, why the bonus for holding Moses, Aaron and Ramses? You could label the bonus "Audience with the Pharoah" (or something shorter that fits in the space

). That would make the map come alive, I think, in ways that are lacking to anyone who hasn't read Exodus.
Gilgamesh is a good example of an ancient text come to life. I've never read it -I never even heard of it until I saw the map in fact- but the labelling of the "Challenges" and the names of the regions evoked a sense of perilous, epic barbarian adventure, and of course the flavor text in the header helped as well.
You've got some good elements of the tale here- Pillars of Fire & Cloud, Plagues, Israel's Journey, and the Snakes. But I think the gameplay bonuses are still hazy in regards to story.
Back to the Plagues... maybe, connect them with Moses directly? Say like this:
Hold Plague = -1
Hold Plague + Relevant City = 0
Hold Plague + Relevant City + Moses = +whatever (1 or 2 I'm thinking)
Moses and Aaron can bombard the Plagues.
Moses can one-way attack any Plague.
This would save on legend space, especially if you used a graphical way to match Plagues with a city (or cities). And also, it would show story-wise that Moses could both 'start' the plague and 'end' it (with the bombard).
Or you don't have to do bonuses at all, but just make the Plagues an attack vector, like so:
Moses or Aaron -> any Plague -> bombards certain cities/areas
I've one other thing to comment on, and that's the 4-symbol bonus for +3. It's semi-good for story, but needlessly confusing for players I think. They need to match 4 symbols for 1 bonus; these symbols are not re-used in other bonuses. Normally, such a bonus would require only 1 unifying symbol. Is it possible to relegate those 4 symbols to just flavor on the map, maybe as text... and use 1 symbol to designate the bonus?
Anyway, best of luck and I'm avidly following your progress.
Marshal Ney