Thief: The Dark Project.
Ghost runs.
I've played through several of the early levels of that game without anyone seeing me or hearing a single footstep (I've used a couple of arrows as distractions though), and without killing or sapping anyone. Had to knock out a few guards or make some enemies "disappear" later in the game, but never got spotted for most of it.
Assassin's Creed and Assassin's Creed 2.
Most recently with AC2, a couple of friends enjoy watching me play occasionally, so I get them to tell me who to kill and how.
"Those 4 guards, hidden blades only"
"Easy" Walk up, double blade the pair on one side, then finish the other 2 while they're still drawing their weapons.
"Fine. The brute in that patrol, then get away without any more deaths. And no poison."
If I get hit by a guard at any point, I consider myself dead and we change game or pass the controller on, depending which friend it is.
Way of the Samurai 3.
I've recently done a run bare-handed only. It's rather interesting. Impractical even on Easy until you've unlocked a few of the higher-level bare-hand moves, but it's a nice challenge. I'm still trying to work out which part of your hand is the "blunt" edge though. That game is weird sometimes...
Red Faction: Guerrilla. Stealth. I did the "snipers on the roof" mission using only the Rail Driver. Didn't take a single hit from an enemy. I quite enjoy being sneaky in that game. At least until I set off the explosives that kill almost every EDF soldier in the area.