In most video games, the player's character is powerful enough to mow down enemies left and right. They don't have to worry about setting alarms off, or enemy reinforcements being summoned (true, there are occasionally levels where you have to be a bit careful, but those are specifically scripted).
In a Stealth-Based Game, the player's character is simply too weak to survive a head to head confrontation with his enemies most of the time. Either it's too easy to die, you can't carry enough ammo, or there is some other reason. Just running away from enemies like in Pac-Man isn't enough to count as a stealth-based game; you need to be actively hiding from them.
Whatever it is though, they've got to be careful, stick to the shadows, kill silently, and only when necessary. And they better hide the bodies well because someone is going to stumble over them otherwise.
The different types of stealth used can be broken up as such, though many are often hybrids.
Line-of-sight breaking: Horizontally or vertically, stay out of view.
Moving through shadows: Avoiding the light, creating darkness to move through.
Hidden in plain sight: As part of the crowd or as part of the scenery.
007: From Russia with Love zigzags in and out of the genre. It's generally easier and more efficient on the on-foot levels to play it this way, but the vehicle levels are more of a blast-everything-in-sight type deal.
Alpha Protocol: The game is designed so that the player can play it as a stealth game, a shooter or a hybrid.
Ape Escape allows you to sneak up on many of the monkeys you're required to catch by crawling around and staying out of sight. Stealth isn't required, and it's possible to play the game like a standard action platformer. However, if a monkey sees you, they'll try to run away so keeping yourself hidden is often ideal.
The Classroom and its sequels, Flash games where the objective is to cheat on tests without getting caught.
Commandos: A game series where in each game a group of soldiers are controlled from an aerial view. Each soldier is extremely fragile, and the maps are filled to the brim with enemies, making clever use of each soldier's special abilities to avoid detection central to the gameplay. Most stealth is in the form of line-of-sight breaking.
Death to Spies: A World War II game where you need to infiltrate enemy locations to complete tasks. Stealth is handled by wearing enemy uniforms, and trying to complete objectives. The stealth portion is difficult as there's bound to be at least one person specifically watching over the only route to the objective, who is likewise being watched. The ideal rank is based on factors concerning combat (using non-noisy weapons), aggression (kill as few as possible), noise (minimize alarms or spread of information), professionalism (using non-cold weapons, or mis-using hot-weapons depending on uniform), and precision (accuracy; only a factor for professionalism).
Desperados: A Wild West clone of Commandos; the player views the game from above, and must carefully navigate a group of outlaws, each with their own special abilities, through hostile territory without drawing too much notice.
Deus Ex franchise: Every game in the franchise can be played as a full-out stealth game, as a shooter, or a hybrid. The games encourage at least some stealth, however. The games in this franchise include:
Dishonored: A first-person game that allows the player to sneak or fight in close combat, but which heavily encourages sneaking. Heavily inspired by Deus Ex, in that exploration is possible and multiple paths are usually available through a level. Sneaking is done by breaking line-of-sight and staying in shadows.
Fear Effect doesn't force you to be stealthy, but it will almost certainly be preferable to attempting to use the control system in a real firefight. There are also a handful of missions where guns are not an option, and the emphasis is timing your movements to evade detection.
Hitman. Here the emphasis is strictly on the use of disguises and not appearing suspicious; as noted in the description, you're generally operating in a crowded area until you reach your target.
Invisible, Inc.: You can take out guards by killing them or knocking them unconscious, depending on your equipment, but it's usually better to avoid it unless necessary. Guards are fitted with heartrate monitors that increase the security level if they die, and KO'd guards will wake up in a few turns and start searching for you.
Legacy of Kain has occasional elements (in Soul Reaver and its sequel, you can get a one-hit kill if you catch an enemy unawares), but it's most prominent in Blood Omen 2, which lets Kain turn invisible when he's in mist, and has a whole stealth kill system associated with it.
Lupin III, from the perspective of the thief players.
Mark Of The Ninja: A 2D platformer where the player character is a ninja. Stealth comes from breaking line-of-sight, staying in shadows and making as little noise as possible.
Messiah: Action Adventure where the player character, a small cherub, possesses various people to blend in. The stealth mechanics primarily rely on the player hiding in plain sight, as a result, although on higher difficulties, targets can only be possessed when their backs are turned, necessitating line-of-sight breaking as well.
Mark of Kri and Rise of the Kasai are a mix of this and Hack and Slash. The games don't force you to be stealthy, and you're tough enough to fight your way through, but stealth is usually the prefered choice and generally makes things easier.
Sniper Elite V2 - Get to the vantage point, eliminate the target, defend your position, and get the hell out of dodge. Unlike many of these games, there's no way to take out enemies non-lethally, though there isn't much point since you're in a war zone.
Tenchu: The first 3D stealth game, as it was released a few months before Metal Gear Solid and Thief. It's notable for its more accurate depiction of a true ninja and for popularizing the stealth kill.
Thief: This game pretty much launched the modern stealth genre all on its own; it coincidentally came out around the same time as Metal Gear Solid. Unlike Metal Gear Solid, this game really requires stealth over combat.