Some of you have strange ideas of what blowing the crap out of stuff means...
"Blowing the crap out of stuff" = "Blowing Stuff Up" (with guns, bombs etc.)
Rampage? Carmeggeddon? Dungeon Fighter? Killer Instinct?!?
As for Worms, Lemmings, not action oriented enough
Blast Corps is a great suggestion, I love that game back in the day, especially with the games drought on the N64 at the time.
Some other good suggestions too, will take a look
Oh and as for GTA, never been a fan, just find them a tad boring, too open ended.
Keep em coming