Okay, so here are my thoughts so far.
My primary enjoyment from Mario comes from the joy of movement. More specifically, from "jumping to not die". Not constantly, but for me there's a sweetspot of difficulty, probably around world 6-8 in a traditional Mario game. I want to beat a level in 5 tries.
I don't want to solve a puzzle. Sorry if that's your thing. I have never liked fixed-solution puzzle solving. I want some freedom of expression in how I tackle a level's obstacles. More Tetris, less that Rush Hour board game where you try to slide your car out of gridlock.
I don't want to be able to entirely circumvent a level's obstacles. So many levels can be beaten by hopping into a Lakitu cloud, and it's not satisfying at all. If you have flying in your level, have it change the way you interact with the level, not eliminate interaction.
To this end, my first level gave you the NSMB Propellor suit. It's an underground level, with a ceiling, so there's only so far you can go. Moreover, if you use the propellor suit, you encounter different dangers than you do without it. There are heat-seaking bullet bills that only really trigger if you use the suit. You have more maneuverability (and two secret areas to access), but additional dangers. Obviously the level can be completed entirely as small Mario. No fixed solutions.
Flight is fun in Mario, but not when you use it to interact with the level. My favorite things when playing the NSMB levels was to try and hold on to the flying powers for as long as possible. To use them on stages where you weren't necessarily intended to have them. You can beat it without them, but the level changes when you're flying around.
For me, I want to reward players with fun. The joy of movement. It should ideally be fun to play a level a second time. I've played through World 1 of SMB3 countless times, and it's always a joy. That's what I want to see captured in Mario Maker design.