I've tried every Hitman game. The demo of every Hitman game, at least. And all it does is make me dislike Eidos / IO Interactive that much more because playing a badass hitman would be just about the coolest thing ever IF DONE RIGHT.
And by right I'm talking about a game that plays and controls smoothly, a game that gives me real research on the target I'm taking out and a somewhat free-form-way to take my assignment out.
To be honest with you, it sounds like you haven't really given the Hitman series much of a chance, because what you describe you want is pretty much what the Hitman series is.
Your comment about hand-holding couldn't be farther from the truth. At least in Hitman 2 and 3, you're essentially deposited in a level where you are assigned a target. You then have to wander through the level, find the target and eliminate him.
There's nothing at all linear about how you take down the target. First off, you're rated on how well you complete your mission. You can actually go through the entire game pretty quickly if you just find the target pull out a gun and blow him away and then race for the exit point. It's a viable strategy, but not the most fun way to play the game.
To get the top rating you have to find your man, take him out and dispose of the body where no one can find it and escape the level all without being detected. The levels always have multiple ways to complete your objectives and, most importantly, getting the highest rating is extremely difficult.
They're decent games. The series is certainly far more open-ended than Splinter Cell, for example. I thought the first couple of games did have some gratuitious sex and violence, but the core gameplay is sound.