Ooh, I can just imagine making Mordor.
I have some ideas:
1. Something based on Dante's Divine Comedy. Nine layers of Hell, Purgatory, or ten Heavens. If you haven't read Dante, I recommend this translation:
Dante; Poetry of Dante Alighieri; full text of Dante's Divine Comedy - Inferno, Purgatorio, Paradiso, at everypoet.com
2. Something ancient-themed. Maybe an ancient Greek city, or mount Olympus, or something ancient Egyptian, or maybe even something ancient native american, you know, like Olmec or Maya.
3. The warcraft world a few hundred years later. That is, the warcraft world seems to be pretty medieval. What would it look like as a Renaissance world? I'd love to see what sort of stuff the horde would be building.
4. Something like "The Prison of the Titans!" Basically just designing an epic prison for the Dark Gods.
5. Something based on mythology. I guess this is kind of like no. 2, but this one would have more things like the dwelling places of the Gods, or the Underworld.
6. Palace theme. Basically making a dwelling-place for a ruler of some society. The idea would be to make it as decadent as possible, in terms of decoration.
7. Place of worship. Temple, altar, church, whichever. The objective is to make interior, exterior, and surrounding landscape of a place of worship for a certain religion (not necessarily an existing one).
8. Prehistoric. The landscape of the worlds of cavemen, mammoths, dinosaurs, the first land-creatures, or the ancient creatures of the sea.
9. Cataclysm. A cataclysmic scene of destruction. The events or aftermath of something such as a volcano, war, earthquake, hurricane, tornado, or anything else you can think of.