While I don't have any in mind, you need to remember that the storyline needs to be practical. Think of one that will give you a lot of different questing options and a variety of enemies/activities. Contrary to what others tell you, taking a cliche'd RPG storyline (Undead/Demon invasion, Bandits, etc.) isn't really as bad as they'd lead you to believe, so long as you mix it up a bit.
Lastly, I found any Wc3 map's attempt at being in any way "deep", "atmospheric" or "thought provoking" in any way fails miserably, while a lot of maps tilted to be more light hearted or humorous work much better. Warcraft 3's visuals complement this well.
So in summary, go for a practical, engaging storyline (mixing it up if it's a cliche) that doesn't take itself too seriously.