SMB "tutorial" through gameplay worked because it has simple buttons (hardware wise) meanwhile your game in the other hand is made for computer where buttons are more complex since keyboard have a lot of it. Movement wise, mario's simple buttons are also tied with it's movements: there's no double jump in original SMB and people naturally shoot fireball when they try pressing the other button. It comes naturally and people don't have to find out any "hidden" mechanic behind those buttons (like finding out if pressing the button again in mid air might do something or not)
I'd say to take a different level design and control approach if you want to apply the simplistic no tutorial style since it definitely don't match the "open world" level model you're going for right now.
Best on luck on your craft and continuing it!