i would go for creative level design. seeing the same level layout with possibly different blocks, colors, or whatever can get really boring really quick. as far as difficulty goes, it really depends. i expect the difficulty of the levels to vary some but only when it makes sense.

level 99 should be harder than level 1.

- What kinds of puzzles?
I can't just name one kind of puzzle that you should stick to since we want variation. However I can name a few puzzles I don't want to see.

Puzzles which has the player backtrack a lot should he make a mistake should be kept at a minimum. There are some in Super Mario World ghost houses, but few or none outside of them. Even in ghost houses, if you have to backtrack it takes a short time to get into position for a new try.

If puzzles are in levels with multiple other obstacles, they shouldn't be very hard. If a player faces ten obstacles and they are so hard he has a 50% chance of passing each, the chance of passing all of them is less than 0,1%. Even if he gets better and can now pass them with a 75% chance, it's still less than 6% to pass all of them. You could have one hard puzzle along with other less hard obstacles, but then you should design the stage around that decision.

- How much difficulty?
Harder than Super Mario World of course. However, while I want to be challenged, I don't want to be frustrated. Since we all have a different level of skill and it's hard to define a quantity of difficulty in the first place, I can't really say "this hard". However, I can say this; the more time a player spent on a stage, the more likely said player is to wanna move on after beating it. For that reason, you may want to make the heavily exploration based stages a bit easier and the less explory stages harder.

Also, I don't want difficulty that the characters aren't designed to deal with. If you give me equipment for hunting tigers and want to challenge me, make me face an extra stealthy and tough tiger, not a swarm of killer bees.