Open world with proceduraly generated boss encounters and story sequences (although I suspect they're over selling the feature a bit, no way they've got billions of lines of dialogue for non scripted story sequences).
From the gamespot preview:
Through it all, Shadow of Mordor simulates the consequences of holes left in orcish social structure, and offers you choices in how you want to further disrupt it. I joined other press members in directing a stretch of open-world play, choosing how Talion should use the information he gathered from squealers to identify the best path towards vanquishing their leaders. When accessing the hierarchical ladder during interrogation, you can unveil heretofore unidentified combatants, or gather more information about the personalities and combat weaknesses of known enemies. Should your target be a warchief, you might get additional feedback about how to lure him from the safety of his lair. And as you slice and dice your way about Mordor, orcs go about their daily lives and react to the cracks in their order. Enemies have their own missions: they organize and throw feasts, conduct public executions, and so forth. The orcs that succeed in their tasks rise up in the ranks, taking the place of fallen comrades and, in turn, providing you with new orcish fodder to extinguish.
There's certainly some jank in there but they've got some ambitious ideas. Do you think they can pull it off?