God of War is a textbook tragedy. At least, the first one is. The one thing Kratos is fighting for, inner peace, is never achieved. What more, its implied he can NEVER find it, no matter what he does. His violent nature and terrible strength, the very thing that won him his greatest victory and should have granted his freedom, also condemns him. He'll have to carry his sins and dreams with him for the rest of his life. You have to remember, this revelation was bad enough to make him want to kill himself. And now he has eternal life as the God of War. Sure he has omnipotence, but at what cost? Of course, GoW II and especially III crap all over this, but what can you do.
Red Dead Redemption is another good example. John Marston is fully repentant for his outlaw lifestyle, and is genuinely interested in going straight, starting a farm, raising a family and leaving everything else behind him. But the only way he can do it is by constantly returning to his outlaw routes and skills. And in the end, this damns him (and a good chunk of the people around him).
The key behind both of these is that the traits we admire in them, and the traits that ultimately damn them are one in the same. Kratos' tenacity and aggression label him as a Nietzschian superman. Not even death can hold him back from his purpose. Marston genuinely wants to do right, even though the only methods he knows are wrong. Their salvation could come at the removal of these aspects of their personalities, but it would come at the cost of what made them great in the first place. Likewise, both of their dooms are predetermined, and the viewer sees them coming from a mile-away, even if the character is blinded by trust or hope. Its like watching a long, sad trainwreck that you can do nothing about.
As for other good tragedies...the Prince of Persia: Sands of Time trilogy works pretty well, though it really doesn't hit until the third game. The Darkness, as well, though Jackie doesn't so much unwittingly walk towards his doom so much as sprint full on into it, being more of a case of "don't deal with the devil" than a tragedy.
There is a problem here though, in that I don't think many people understand the definition of a tragedy. Bad things happening to the heroes isn't a tragedy. The bad guys winning isn't a tragedy. They are just sad. A tragedy is an unavoidable loss because the defeat is ultimately tied to the elements that make the heroes heroic. Hell, a tragedy can have a happy ending if the heroes "gets it" by the end. Gurren Lagaan, despite all its silliness, is a good example. Its not an unhappy story, but Simon does get screwed over and over thanks to Spiral Energy. But instead of saying "screw it", taking on the universe head-on Spiral King style, he decides to reascend and lives the life of a humble traveler, avoiding whatever doom may have been awaiting him.
