Unreal Tournament Series and the first Unreal (the former one is more online fun the latter is more story based)

Rainbow Six plus Ghost Recon Series (more tactical than arcadey but still great)

F.E.A.R 1

Oddworld Stranger's Wrath

Also look into the Tom Clancy games here.

Your buddies are correct I don´t know about the bugs but, the AI, after having played one of the modern ones is still leaps and bounds better. To me at least it keeps being the best of their kind.

Doom is still the best shooter ever.

If it ever comes to GOG, I will fist-pump the heavens so hard the firmament will break.

I remember the marathon lan party we had when Croteam released the first Serious Sam game as it was yesterday.
16 player co-op, on high difficulty. The mayhem. The madness. And finding every little secret the game had in it.

The game i'm always returning to is UT99. Jailbreak, sniper, instagib, CTF with relics. And the servers is still pretty much alive.

I also have very fond memories of Quake with Hipnotic and Malice
(Damn you, ID for selling out to the vogons at Zenimax) ;p

Not a big FPS payer but I love Painkiller.

If you're looking for some Fast FPS like Duke Nukem, you'll be disappointed playing ArmA.

ArmA is a real simulation, not really a FPS. You've to check the map, plan your objectives, plan your movements before launch the mission, take care of your team, take your time to check enemies position, etc...
ArmA is a wonderful game, one of the best GOG game IMO, but be sure to enjoy this kind of gameplay before buying. And yes, peoples are still playing it online. Not a lot of servers available, but you can find some online play without a lot of problems.

And to answer your question, for me ArmA series is the best choice here on GOG, but I said it's not really a FPS, so I'll say Painkiller (the best Fast FPS ever with Doom and Quake), Postal 2 (WTF total), Far Cry (Do I have to speak about it ? Seriously ?).
A little speak about Sniper Elite : if you like sniping and be stealth, this one is a good choice :-)

CS GO
CS GO
CS GO

The Marathon trilogy. Best FPS's I've ever played.

F.E.A.R. is good. The expansions and sequels are not.

I've always been a Battlefield 2 fan.

Someone mentioned S.T.A.L.K.E.R. Call of Pripyat, that is a good one.

I am also a fan of the Quake series, can't really go wrong with any of them or Unreal series (I think UT 1999 is better than Q III).

The Medal of Honor series has always been a favorite of mine, special mentions for Airborne and Pacific Assault, but Allied Assault's good (although it never gave me any trouble, I've heard that Airborne has SecuROM, so fair warning).

Halo on PC is okay, better than Xbox anyway.

Delta Force games are also good, my favorite is Black Hawk Down, Xtreme is good, and though not speaking from experience I hear a lot good about the older games.

Finally, I am hard pressed to think of a mid-late 90s-early 2k shooter I do not like, be it Rise of the Triad to Serious Sam or Return to Castle Wolfenstein.

The strange thing is I don't really consider myself a fan of FPS.

Blood - my all time favorite FPS.
XIII - stealth / shooter hybrid with interesting comics-like graphics + Adam West.
Painkiller - crazy, shooting, fun time.
Serious Sam - see above ^-^.

Descent 1
Descent 2
Descent 3

Fast Eddie Felson.

Oh, you mean game.

Man that's tough. While lacking in elements of gameplay I like a setting I can relate to in the sense that I see objects I recognize, like actual buildings. Games like Quake 4 while far superior in game play lose points with me because the setting is so alien literally and non. So it's a toss up between the original Medal of Honor and the 1st two levels of Duke 3D. It may sound beyond stupid but being able to walk into a recognizable everyday bar or pool hall or even bathroom and start blasting is just the coolest for me.

EDIT: SCRATCH THAT!
What was I thinking!? There is only one supreme FPS, well two: NOLF 1 & 2.

Your laptop should be able to run Far Cry smoothly.

Heretic and Hexen + Hexen II were my possibly my favorites.