If you define "puzzle" as a problem that you must work out with hard mental effort, then no; not at all games are puzzles. Rail shooters and other mindless games that rely more on reaction speed would not constitute a puzzle since you don't really need to even think.
Online shooter, sure. You have to think about what the other guy is gonna do. Virtua Cop? You just need to aim and shoot fast when the bad dudes appear. I mean, you could play Counter-Strike like Virtua Cop but you probably aren't gonna be good unless you're posted up with an AWP all the time.
I actually love Metal Gear Solid because its design is much like that of a puzzle game, where the puzzle is "how the fuck do I kill everyone without being seen?" Hitman is the same way, but it always felt less curated than MGS because there isn't just 1 solution to the problem, where as MGS does. And a lot of it is only conveyed through their respective scoring systems.
On the flip side, I tend to dislike leaderboards in most games because there is only 1 possible way to get the maximum possible score for any given level or minigame that once it's worked out, everyone can be at the top and the only way to truly rise above everyone is to cheat.