I'd recommend XIII myself. Very story based. Note that it has checkpoints instead of quicksave-any-time, but I didn't find it very difficult, and I'm not all that good at shooters.

Just tried it out, Work perfectly fine on my Win 7 64-bit

It's one of the most atmospheric shooters ever made. The levels are superb. The bossfights are interesting. And the weapons are something special. The enemies aren't very smart though, and there are usually only 2 or 3 types per level. So it can get monotonous. Sam has a lot more variety. Its main problem is that there's so much combat it becomes draining.

aint it 5 euro?

Painkiller blows Halo out of the water without even batting an eyelash. It's not even a contest. Halflife... well, it's comparable to Halflife in terms of quality, although the two are about as different in philosophy and gameplay as FPSs get.

If you're looking for a GOG FPS with a good story, though, Unreal does a really good job channeling the sort of minimalism of Halflife via the log-based style of System Shock 2. There are some little mini dramas to follow through these logs, and your own experiences and observations of the world end up being the meat of the main plot. Actually quite a success in terms of subtle FPS storytelling.

If you're looking for something a bit more complex I recommend Ghost Recon. The gameplay is slower and requires more thought than most FPS games, but it's satisfying to see your strategies pay off.

Serious Sam, that is all.

I'm looking for a nice military type shooter with a lot of fun, at least semi realistic sniping. By sniping I mean that the game has some parts where your avatar sneaks around in camo with a sniper rifle and picks off the enemy one by one. Any recommendations? A gog game would be nice, but I'm open to non gog games as well.

First of all, Sniper Elite might be worth a shot, but I have never actually played it.

ArmA: Cold War Assault: It's basically a simulator of war. You get shot, there will be consequences, you either instantly die or will have to crawl .. well it's generally unpleasant. And the game gives you a feeling of being part of an army - you feel like you're just a person in all that hell, and nothing really revolves solely around you.

Ghost Recon: You don't have to be a sniper but you get to pick loadout. It's a squad-based tactical shooter, you order your squad around and try to support them as best as you can. You can also switch between members if I remember correctly.