I have a ton of love for True Lies on the SNES. It's not a perfect game by any stretch (it definitely has its flaws), but it's pretty damn fun, especially the first couple of levels.
Biker Mice from Mars on the SNES is another fun game as well. It's sort of similar to Mario Kart in that it's a racing game where you can shoot/screw over the enemy or your buddy playing with you by using your character's attack, with each character having their own unique attack, stats, etc. The main race mode is fun, and you get to upgrade your bike and purchase more attacks or power ups with prize money after each race.
And if you want a game that is absolutely brutally difficult, then you should check out the Adventures of Batman and Robin on the genesis.