A mí The Saboteur, si dominas algo de inglés, me pareció sublime. También en inglés, si sabes ver más allá de la ñoñería, Valkyria Chronicles es fantástico. Y ya en castellano, inFamous es el traslado perfecto del comic al videojuego y Batman Arkham Asylum.
De los que ya te han recomendado, Bioshock mola. Mola mucho. Pero no es una historia "como tal", lo que (siempre en mi opinión, claro) hace grande a Bioshock es todo lo que hay detrás, todo ese retrato político-social, todas esas ideologías, no es sencillo digerirlo de buenas a primeras, y menos si vas sin prestar atención. Bioshock 2 es mucho mas sencillo en ese aspecto, bastante más dinámico y entretenido.
Uncharted, lo que ya te han dicho. A parte de tener una jugabilidad buenísima, tienen historias que enganchan y atrapan. No será de lo mejorcito, pero como juego es muuuy bueno, y la historia eso, engancha, como una peli palomitera.
Como guión, Heavy Rain es espectacular. No tiene eso que tiene Bioshock de dártelo todo en pequeñas dosis y hacerte pensar, sino que lo que ves es lo que hay, pero engancha cosa mala.
Y Metal Gear Solid 4. Si no has jugado a los anteriores, te molará, pero si has jugado a los anteriores, te emocionará. Una genialidad.
Luego tienes los que son de ir explorando y hablando con la peña para descubrirlo todo (Fallout 3, Dragon Age: Origins, Mass Effect 2 (que saldrá a principios del año que viene), pero esos solo molan si vas a ir parándote en cada esquinita a ir hablando con cada personaje, por poco importante que sea.
Y hasta ahí llego. En realidad, juegos con grandes historias no abundan en la generación, pero pienso que nos estamos volviendo bastante exigentes y que cada vez que sale una maravilla, lo ponemos como lo estandar, y eso nos impide disfrutar de cosas entretenidillas (God of War no pasa de entretenido, por favor, Castlevania se lo come con patatas en cuanto a argumento (que no jugabilidad), como el propio God of War, la saga Ratchet & Clank, la mayoría de los shooters con historia (y no me refiero a Call of Duty
)...
EDITO: Vaya, RMB se me ha colado con algunas recomendaciones
, eso me pasa por escribir tochacos...