Civilization still screws me like that, once in a while. It's definitely the game I've spent the most time playing. I have to keep it off my hard drive, if I want to get stuff done.
Bouncing Babies, Ghostbusters II, Leisure Suit Larry, Rick Dangerous 2, the Accolade racing games, Chip's Challenge, Lakers Vs. Celtics, not to mention all the games I played on the Amiga.
So you would also want a film noir style 1930s detective story? The graphics could be Sin City style and you could be a detective solving mysteries and having gunfights with thugs. But not like Mafia, it was good, but this would need to be more detectiv-y.
I think it should be more adventure-like with less shootouts and more holding people at gunpoint. If guns are to be used, it should be in short "one hit kills" style. And one melee hit to the back of the head would knock out everyone.
Also, it should be real time. Like one night where everything goes south for our detective.
I think the problem with game challenge these days is the notion of empowerment that has been developing in the industry. Apparently, for many game developers "empowering the player" means giving the player everything on a silver platter instead of giving the player a challenge and varied tools to overcome said challenge. It's the old "giving a fish/giving a fishing rod" dilemma, I guess. Specifically regarding RPGs, good endings should be considerably harder to get than bad endings.