Good evening everybody :)
Did you ever play "among the sleep" ? How is it ?...

IAmSinister already mentioned Escape Goat which is really a great series. The normal story levels are quite easy and should be doable for everyone while the bonus levels are a real challenge. But please be aware that it's not a pure puzzle game. You will also need some platform skills.

A game that I like very much is Block That Matters. Puzzles are completely logical, but you will have to use your brain to find the solution in some levels (especially if you play for perfect 100%). Again bonus levels are more challenging. There are also hundreds of community levels if you want more after you completed the normal game and an editor to build own levels. Again some platform elements are included and there are also three "action levels" that might be annoying if you are just interested in the puzzle elements of the game.

The sequel Tetrobot & Co. is also very good. It's a pure puzzle game and the good thing is that it should be doable for everyone. If you just want to complete a level it's not very hard, if you want to collect all the memory blocks, it gets a lot harder (you need a certain amount to get to the next area).

My favourite puzzle game series is DROD, but I would say that it's quite hard. In theory you could plan very thoroughly and solve each room on your first try. But in reality you will die many, many, many times, because you overlooked a small detail and one of the monsters will kill you. But when you finally complete a tough level, it's very rewarding and completing a whole game will give you the feeling that you really archieved something. You can spend hundreds of hours with this series and if you still don't have enough after that, there is ton of community holds to go on.
For beginners I would recommend the fourth game DROD: Gunthro and the Epic Blunder, because it's the easiest one in the series and kind of DROD lite.

And the last game I want to recommend is Spacechem. Also completely logical, but also very hard (I wasn't able to finish it by now).

I know I also played a lot of puzzle games in the ten years in which I only played freeware, but that was quite some time ago and I have to look for the titles of some good ones, because I can't recall them.

Well, if a Viking is telling me I should get a game that includes lots and lots of melee combat, it must be good. Will retrieve that next, thank you. =)

Additional - Among The Sleep is up. 11.99, 40 percent off. Smugglers V to follow.

As others have said, you'll have to get it in a bundle. GOG made the mistake (last year?) of running a sale where they had a game (Strike Suit Zero, I believe) both in a flash sale *and* in a bundle sale later at a higher discount. The peasants were revolting (double meaning intended). It was not pretty at all. I think GOG learned their lesson so that will not happen again.

I forgot to say that I got the first game when it came out and it definitely takes a hold. I find myself going back to it to clobber some more vermin. It would be great if there was a pirate version where you could capture ships, catch scurvy and throw up over the side.
Thanks, Mr Cookie Monster!!

Try Escape Goat 2. It's beautiful, and better in pretty much every way. And if you love it as much as I do, you'll have no problem going back to the first one for more, no matter what it looks like. :)

Q.U.B.E. is not a bad puzzle game, if you're looking for one on sale. And MouseCraft is enjoyable too, though I've only played the beta and haven't gotten to the released version yet. InFlux is pretty but I found it rather dull.

I very much enjoyed MIND: Path to Thalamus, but it's also strange and artistic, so you have to decide if such a thing is right for you. But at its heart it is a puzzle game, and a rather good one.

Agreed! I still hope to see the original released on GOG eventually.

The Journeyman Project keeps tempting me. I'll get dinner before I cave in.

There's a great free puzzler called Stealth Bastard, Tactical Espionage Arsehole, which Steam has in the form of the later Stealth Bastard Deluxe. The freebie should be around somewhere, although the link on the SB site is dead. Really worth a go if you can find it, if for nothing more than a good giggle.

Then you can blame digestion for low brain activity and not feel guilty, right? ;-P

On the subject of puzzles, here's something that might be of interest - http://fools-errand.com/
First heard about the game Fool's Errand years ago. But now, the creator of the game has not only that but two other games he created on his site for free and legal download, along with free emulation software to run them.

Thanks for your long answer! I definitely remember the first DROD games, they look quite good and even have a Linux version. I already was about to buy them, but then there obviously came other priorities. ;) And I already have Spacechem, sadly not yet played. Have to raise it on the to-play list. :) But both games got into my focus more as an RPG resp. strategy game, not so much as puzzle games. Good to know I can train my puzzle skills there too. :) Your other recommendations I have to look up. They are probably more "real" puzzle games, which I have mostly ignored so far.

Would be nice to know too.

You can download it here

I can also recommend it, but it's not a pure puzzle game. You also need some serious platform skills to get through the game. The commercial version Stealth Bastard Deluxe was DRM-free in a Humble Bundle a while ago. Not sure if you can still get it DRM-free at the Humble Store. If you can it's worth every cent. Would buy another copy on GOG if they ever release it here. Even if the end is so sad that I nearly cried.

You can. It also comes with the Android port.

I sure hope System Shock 2 goes back down to $2.00 again. I have $3.00 left on my AE Gift Card. lol.