[WitchOfDoubt]

A lot of these recommendations are great, but here are a few that haven't been made yet:

There are some fantastic detective games out there if you know where to look, especially if you include text adventures. I strongly recommend the freeware adventure Make It Good, by Jon Ingold - a tough but thrilling mystery thriller where you play a good-for-nothing drunk cop. There's no way anybody's going to solve it on the first play-through, but it's REALLY rewarding when you do get it, and the richness of the character interaction is incredible. People don't just react to what you show them, they react to what you're carrying and what you've told other suspects.

The Fedora Spade freeware games are a little crude sometimes, but also have some rewarding puzzles.

If you're willing to go even further afield of conventional adventure games, the sound novel Umineko no Naku Koro ni has almost no interactivity until the final episode, but is most definitely a game. In matching wits with the characters, a good reader will try to solve a series of locked-room mysteries that may or may not be fair puzzles. The game doesn't prompt you to solve them explicitly - you could just press Enter for hours and hours and hours, waiting in vain for the game to give you the answers - but there's an implicit challenge in it, just like reading a bizarre mystery novel. (Ignore the animated adaptation; it's missing the clues you need to make sense of anything.)