Here are some suggestions that would be different enough that they might make things interesting:

 - Swamps. This works best if they are bog-like and have islands of solid ground linked by pathways that are surrounded by quicksand/mud/water. This also allows for unexpected surprises if they get too close to the edges.
 - Rooftops of a city. Say, for whatever reason that the ground levels of the city have been abandoned due to a poisonous cloud-type spell gone awry, and that the rooftops are occasionally connected by planks and other such things. If it is a recent occurrence, and the planks are weak enough, a given path may look feasible, but may be treacherous for the person wearing 30 lbs of armor and another 20 lbs of weaponry.
 - Forest paths that have been worked by the inhabitants to form paths, rooms, etc. Bonus points for the creatures to be small and be able to move from one path to another through very small holes in the forest "walls" of the paths that the PCs can't get through.

_edit to add_  
 - How about a city after a serious battle? Lots of streets could be booby-trapped, be filled with impassable rubble, or have some fighting or barricades that they need to find a way around.  
 - In a similar fashion to the swamp above, how about a desert with sinkholes, or a filed of geysers and really hot water?