My favorite game of all time is Fable, for sure. A little old, but well worth playing if you haven't.
But as for some more recent offerings. Assassin's Creed was a lot of fun, the only thing is that it gets fairly repetitive. All the missions are generally similar, and for some reason with the exception of eavesdropping, most of the tactics are not at all subtle. Though, I could've just been playing wrong, hah! Well worth beating though, the story gets interesting.
If you have a PS3, I highly recommend checking out Infamous. It has that morality counter, which changes the story of the game. Even though some of the choices are fairly obvious (ex. Using your powers to start a riot), it's pretty neat. The gameplay itself includes a little bit of everything, without feeling like the developer was trying to stuff everything in: Platformer, FPS, third person action.