I can't quite recall which exactly was my first Mario experience. I remember playing a lot of Mario Paint when I was super young, but growing up, I know we also had multiple NES systems that we basically always had Super Mario Bros. for as a staple game (with Duck Hunt, of course). Although my memories only really stretch back to Mario Paint, that doesn't mean I didn't play SMB first. It's a real toss up, but it's definitely one of the two.
Other early Mario titles for me include Mario's Time Machine (I know lol) and Super Mario World.