Sadly, there is no "puzzle" category on GOG.com (and no, "simulation" does NOT count).

Are there any great Puzzle Games that you guys would recommend?

I'm already a big fan of "The Incredible Machine", so anything along those lines would be fantastic.

Crystal Cave is really cool and challenging.

There is one puzzle game that I really loved back then : Push Over.

You could try the Commandos series. The Commandos games are essentially puzzle games even though they superficially look like real-time tactics games.

Fish Fillets. Originally a commercial game, has been rewritten as open source and made freely available: fillets.sourceforge.net

It's an *extremely* challenging game, and it's also fun. Nice animated graphics, jokes and all. :-) When it was first released, the publisher offered a gaming PC as a prize for the first complete solution.