WARNING: If Legolas dwarf-hopping and dual-wielding pisses you off, you might want to stay far away from this video. I just stumbled on it yesterday and although it looks very derivative of Assassin's Creed and the Batman Arkham games, I was impressed on a few fronts:
Official Middle-earth: Shadow of Mordor Gameplay Walkthrough - YouTube
Overall it just looks fun and the real time animation/lighting is pretty sexy. The procedurally generated elements of the story sounds nice and I like the Mafia tree with the relationships between the Orc commanders.
Can't say if I'm gonna pre-order it tomorrow but I will keep an eye on it.