Super Mario: Magnum Opus is a game that takes the "Mario With a Gun" premise and runs with it. Not only does Mario have a gun, and that gun gives Mario some nice movement options, but so do the enemies, each with their own different shot types to dodge.
When mentions of a third Mario brother came up, I was iffy, but was pleasantly surprised that the game made it work. I won't spoil the story; it's a short and sweet fan game you can probably clear in about an hour, and does save your progress if you need to take a break.