I'll agree that the redemption thing goes amiss for the story, but it kinda fits with the character's mentality, though. In his single moment of failure, he calls upon the God of War (Patron of Sparta, let us not forget) to destroy his enemies, and make him into what can more or less be described as the pinnacle of human physical combat. He vows to be the personal servant of Ares in exchange for beating down some barbarians, and Ares isn't exactly the kind of guy to have weak servants running around. The only time he feels remorse is when something close to him gets killed by an unfair means, which usually means his soldiers killed without being able to fight. Any highly militaristic commander would be equally upset, and would strike out with strength and ferocity against those that did him a wrong. The business with his family was the premise for his servitude to Athena, and the ending of his service to Ares.
When he runs the god through, though, you have to see it from his perspective. One of the most pugilistic societies had raised him to always want more, to always be the best, and to never fear any obstacle. A man like this with an entire nation of strong soldiers willing to follow him and fight for him has only a few options--living peacefully with everything isn't one of them. Suddenly, he's got power, and lots of it. He's got a host of god-given magics that he can call upon, the experience and title to make anyone around cower before the mere mention of his sandals, and nothing more important to do that reign over warfare. He alone had climbed to the top of the temple, solved and survived the puzzles, and ripped many beasts to shreds with his hands. And now, with all this power, he's got nothing to do.
So what would you do, with power bordering on the omnipotent, a spiffy new title after killing a god, and an entire army hanging about on your resume?
Well, you go fuck shit up, that's what. And, in lieu of anything more challenging or pressing, that's what Kratos does. He goes, unstoppable, with his ego burning hotter than the Prometheus pyre, and finds out he's not as all powerful as he thought. And, upon a quick saving grace from the Titans, he gets back up, unafraid, and has something else to do, now--fuck up something, someone, specific. It's the old "what do you do with your super soldiers when they thing they have to kill is now dead?" question, and it's the story of watching what happens when said super soldier has nothing to do.
So, while the story might not be the most award winning, it is still the story. With nothing else to really lose that matters personally to him, Kratos goes for his vengeance for removing him from his seat of power. Raw power, blind anger, an impressively vindictive intellect, and unimaginable cruelty (well, they did give us that second person kill, of watching him beat the shit out of the cameraPoseidon, so not unimaginable, I suppose) are the tools the man uses when he needs to get something done, and they are tools he's quite familiar with. By the second and third games, he's not seeking redemption, for he's come to understand that there is no redemption for him. And with that in hand, he goes to do what he does best--fuck shit up.
When he meets Pandora, he thinks he can use her as a scapegoat towards redemption, to no avail though. At the point of choice, where he could have redeemed himself, he got the bloodlust and began the process of opening up Zeus' face, releasing Pandora into the fire. He realizes there is not redemption, just personal satisfaction, and that's all he needs anymore. In his two moments of being nice, he tries to commit suicide, and is stopped both times. As for the gods...well, they were in his way. He removed them, as he knows best how to do. His entire function, from the time he was the captain of the army to the time he was painting the screen red was, point and fact, to be as brutal as possible in the execution of his duties. Without duty, all you have is, well...fucking shit up.