ok so I agree with your explanation of linearity to some extend..... but then i'll extend that non of your examples are non linear.... half life you might be able to use the physics but you still have to go from point A to point B killing stuff... deus ex pretty much the same except you have 3 different path to do it..... hitman same too.... I mean mass effect even broken down is less linear than any of those supposed non linear games you named.... this game has more replayability with more variation than any of the game you said are non linear..... same goes for assassin creed to some extend..... and even if I def agree with GoW being linear i don't see how HL is not too... I mean I might be able to take slightly different route but beside that using different weapons and tactical approach is possible in both....
thinking about beside RPG like fallout or the elder scroll I don't know that many games that are really non linear by deffinition.....
but non linearity doesn't equal better replayability and classic award..... look at the real classics of all time 90% are more linear than any of those blockbuster game you named for being linear.... look at Sonic, Mario, R-type, Gallaga, time crisis, pong, snake, tetris ( i mean tetris come on you can't be more linear, yet people play and replay it again and again and even get different version of it)....

Good point. I hate that too. It breaks the immersion.

and you forgot that a lot of the linear title you named are classics or on their way to be because of multiplayer..... yeah people don't play gears campain 20 time over.... but they do play a shit load more hours online at the end than any of the supposed non linear game you speak of..... so the value per minute played is still way higher.... with the exception of those few open RPG.....

yeah but if you compare AC to Red Dead Redemption, you'll notice that RDR has more freedom, and actually let YOU decide how to finish your missions.

i'm not talking about multiplayer, multiplayer never make a game, since the newest games often have the best multiplayer even if their single player parts are crappy.

Galaxy 1 is definitely the most linear 3D Mario out there as far as the level design goes. But I'd say the brilliance of the level design comes from the multitude of ideas that surround each and every galaxy. I mean, for the most part every galaxy is unlike the one before and after it, and that's what makes it so refreshing. Though I do believe that they realized that Galaxy was a lot more linear than the two previous 3D games, so they added playing as Luigi afterwards (changing the physics of the jumping and running) to increase the replay value. So with that said, I do agree with you that 64 has more replayability to it than Galaxy does, being that its more open.

Many consider Sunshine the weakest 3D Mario because while it has a very non-linear playstyle like Super Mario 64 (maybe even moreso thanks to the movement freedoms that FLUDD provided), the locations and methods of getting the stars were very similar to one another, even across different worlds (Which were also very similar to one another. After all you're not going to find an ice world or a cloud world on a Tropical Island. I think they really limited themselves with Delfino Island). Super Mario 64 had a great balance of being very open ended but also provided levels that provided very different experiences from one another (and thus made things have a better flow). But I would argue that both Galaxys have the most diverse set of worlds to explore and ideas that were executed extremely well.

Galaxy 2 is also very linear in level design (though I'd say not as linear as the first Galaxy) but once again provides a multitude of ideas for each and every galaxy present. You'll rarely find yourself finding a star in a similar fashion to a galaxy you've already beaten. We've had reviewers say that they've encountered more new ideas in a single galaxy in Galaxy 2 then they've seen in some full-priced games in their entirety. You're always kept on your toes, always placed in a new situation and faced with a new way to get to the goal. I'd say that these constant flow of new ideas make both Galaxy's very much unlinear (according to Pullus' definition at least). And let's not forget about Galaxy 2's addition of the Green Star Hunt. This great addition shows that each level has a level of explorability seen in 64 and Sunshine. Some of those stars were very well hidden, and took searching every nook and cranny (and listening for that jingle when a star was nearby) to find. Brilliance man, sheer brilliance!

Well shortcuts in a game like Call of duty would not make much sense.... Welcome in Normandy if you go through that hidden door you will end up immediately at the Berlin level :s;.

To the OP: So what games fit the criteria of a non-linear game exactly?

I'm a fan of linear AND non-linear games.

I liked that Uncharted was fairly straightforward, simply because I enjoyed it at the time I was playing it. I knew I would only need to play it once to get the whole story, but I've replayed it a couple of times just because I wanted to.

There are games that are non-linear (I'm playing DA:Origins just now) that I love too. Its a whole different gaming experience, but I probably couldn't choose between them if I was asked.

I don't think non-linearity should be a negative thing, its just different. As long as I get my fill of both, I'm happy.

It depends on the game