Early FPS' defined the genre, Wolfenstien was little more than mazes with guns and nazis.
Doom 1&2 really took it to the next level, if you were a kid when these games came out, they were the first of thier kind, and were scary as hell, growls and snarls from monsters you couldn't see yet, a basic lighting system all added up to a hell of an experience, one that if you were not there when doom 1&2 hit would be lost on you.
Quake followed up, and while I don't think the series really changed the FPS genre it did keep pushing the envelope for graphics.
Half Life really took the Shooter to the next level, it was scary, it had a good story, and in my opinion was one of the first games where people really took a love to the main character (Gordon Freeman) who with his no dialog and quiet confidence clearly painted the way for Master Chiefs character type. Half Life 1 was amazing, interesting new monster types, cool weaponry etc. Not only was half life amazing but it spawned one of the most sucessful mods in history, counter strike, which eventually got gobbled up and went retail.
For those of you saying Halo, lets get one thing straight, if Halo were not a Console shooter it would have left little t no mark on the FPS genre. It just happened to be the next decent-good shooter for consoles since the amazing Goldeneye(which showed the world that FPS and multiplayer on a console was more than do-able) Halo brought very little to the table in regards to influencing the genre, no stand out mechanics, story line was meh, and the only shining point was that people adored MC, couple this with some of the earliest easy non local console mp and halo has been a sucess. Huge series. Nothing about halo says "Im a genre changer" except maybe showing the world a whole new level of fanboyism, and possibly starting the spark of the console fanboy wars on the level at which they operate now.
As for new FPS games that will make a mark on the genre. Portal is one for sure, love it, or hate it, some say it was too short. Portal brought something new to the genre, good story line, great environment (Behind the testing walls, with all the wall scrawls), great personality to the end boss, and a fantastically comical and catchy end tune. The game play is where it stands out. Nothing has been like portal, it was a completely new experience for FPS players, which was great especially if you’ve been playing FPS games since 1990.
Another Game I’d like to point out is Medal of Honour, sure it’s a tired series but I think they really brought the WW2 genre(Which is played out big time) to a new level. And lead to the countless WW2 shooters.
Just a brief insight into the genre on my part.
And for the guy who said FPS games have no story, you clearly aren't paying attention.