Really there's 3 contenders for this; either 'Gunfighter'/'Showdown in 2100AD', 'Duck Hunt' or 'Super Mario Bros.' It could even be 'A Link to the Past', but I probably played NES before NES. I know exactly what games were my first on handheld and a home computer though; 'Tetris' and 'Star Wars Rebel Assault II' respectively. On home console, I was too young to remember precisely, being probably anywhere from 4 to 6 years old.
'Gunfighter' or otherwise known as 'Showdown in 2100AD' is an old arcade shooter from the 70s, similar to the 2600's 'Outlaw', which I played on my mom's old Philips Videopac G7000 from the '70s, known as the Magnavox Odyssey2 mostly elsewhere. Being born in 1988, the game is a decade older than me, but until my mother got a new man, who was actually interested in technology, it was the only system in our house until the N64 in 1997.
In the mean time though my aunt had the NES and later the SNES, which I played with my cousins. So 'Duck Hunt' was a popular game with us. Since 'Super Mario Bros.' is on the same cartridge, that's automatically a contender but I have less clear memories of that game. As far as I remember, my aunt wouldn't really let us play on the SNES, so that's why I probably didn't play Zelda until later.
Most of my money would be on the G7000 game, or 'Duck Hunt'.