FEAR 1 has lots of different approaches for most areas.

I wouldn't really call that linear versus non-linear. Duke3D is a completely linear game, the exact path to succeed is laid out and you go from key to key to key. The difference between Duke3D and Duke Nukem Forever is more about level design, corridors versus wider spaces. The gameplay is linear in both.

Modern examples of Duke3D, a linear game with open level design, would be Crysis and Crysis 2, FEAR, Farcry and BioShock.

A non-linear game is one where missisions/objectives/goals can be accomplished in a flexible order determined by the player. An RPG with multiple quest paths is non-linear. A shooter where the missions can be selected in any order is non-linear. A shooter where there are multiple ways to get through a level is non-linear.

Examples of non-linear shooters would be Farcry 2, Red Faction Guerrilla and Borderlands.

I think a reason there are so few non-linear pure shooters is that companies prefer to make an RPG hybrid when they take shooters into an open non-linear world. Think Deus Ex or Fallout 3.

STALKER: Call or Pripyat is the best shooter since Team Fortress 2. If you count TF2 in its current state it would be the best shooter since... well the first STALKER.

Wouldn't that make Fallout 3 and New Vegas relevant as well?

IMO, a good example of non-linear pure FPS game (that is: not "contaminated" with RPG elements) is Tribes Vengeance

Is not really modern, beiing 7 years old, but it still looks cool today, and delivers a nice multi-character single player campaign

If you want to go really retro, Marathon Infinity (and the incredible fan-based mod based off of it, Marathon Rubicon) are great examples of non-linear story-driven FPS games.

No. S.T.A.L.K.E.R. has RPG elements but is by any stretch not an actual RPG. It also has adventure elements, that is not to say it is an adventure game as well. In saying that, Fallout 3 and New Vegas work terrible as first person (or third person if you are so inclined) shooters. It is very much balanced towards using VATS and the gunplay is rudimentary at best.

considering there was a thread about it not too long ago. Xenus 2: White gold might be something along the lines.
I know Boiling point, earlier game by the same company, was quite nonlinear FPS affair. Some RPG elements and inventory system. But free roaming, as far as I know you could from you started the game go directly to the area of endgame, not sure if the things for the endgame were there for starters, but you could go there.
Choice of I believe 7 different factions to do work for. Allying yourself with whoever you pleased caused the other factions to get upset and attack you (like GTA 2) and so on and so forth. This is Boiling point, shame about the gameplay mechanics and the fact it crashes whenever I try to change the settings on my Vista x64 machine.

Also someone mentioned Duke 3D. Some of the levels were quite nonlinear, in the way you could bypass sections if you found another way (get rocket launcher, fire through window in first level and you have a hole to bypass a chunk of the level, blow up the screen get jetpack and fly to the end of the level). I actually don't think I ever found the intended route through level 2 in episode 1.

I also agree on stalker. Completed SoC and ClearSky, but not CoP, mainly because just as I left for Yantar (I think it was) my saves got corrupted or something, it's kinda hard to follow the plotline when all subtitles and speech goes missing in the game. Even loading a bit back had this broken.

And regarding Riddick. I'm glad to hear I'm not the only one who found something wrong with the one included in Dark Athena. I thought maybe I was just remembering Butcher Bay wrong, but it seemed a lot less good to play

if by modern you mean make after 2007, The Nameless Mod should suit your needs.
if by modern you mean an engine made after 2007, this won't cut it, seeing as how its a Deus Ex mod.

Interesting, I am playing through Bioshock 2 - Minerva's Den right now and have no idea what hyperbole are you on about.

I played only bioshock 1 and it was crap. There is a typical mouse smoothing activated and that is typical for console ego shooter and thus is crap for a pc player. Also AI, level design and the walt disney style graphics gave me the rest.

Hyperbole galore! Mouse smoothing was disabled in patch, Bioshock 2 and Minerva control perfectly. AI is usual, like in any other game. Design is matter of subjective preference, some love it, some hate it, some are meh to it. I love Art Deco style, so I like it.

Bioshock series is inferior to say, Deus Ex, but compared to most other shooters it is above them.

Bioshock is .... Well, I finished it once and I sort of liked it, I hate how much dos it have in common in System Shock 2, while not copying the elements that made the game legendary. It's like they were on their way to make an amazing way and stopped halfway, thus rendering a lot of players that were expecting a true successor to SS2 angry. It wasn't bad by a long run thou, slash is just trolling

Yeah if they made Bioshock that would take place before Rapture fell, in more Deus Ex/Vampire Bloodlines style, that could be amazing. These shooters they made are great too, but the potential was much bigger.

Le sigh.

If you include console FPSes I'd say The Darkness, made by the Chronicles of Riddick: Buther Bay developers Starbreeze. Sadly it wasn't released on PC, but in level design I'd say it's pretty damn close to the style of Deus Ex (especially the New York section, as The Darkness also takes place there) - i.e., it's linear, but rarely feels cramped, gives you many opportunities to explore the environment and has a few side quests.
Otherwise I think people have pointed out all the modern PC FPSes I can think of. Borderlands is great and probably the most open one you'll get across. I could give another thumbs up for Far Cry 2 though, it's very underappreciated and very non-linear.