Devil May Cry 1 or 3 (2 is kind of lame and unnecessary) and definitely God of War. Resident Evil 4 is also an excellent game. The Prince of Persia games are great too, but be warned, they're very challenging.

I tried MK: Armageddon...not that great, the fatalaties thing is really weird and there are better fighting games out there.