Dynamic levels and overworld screens. You know how in Mega Man X, if you beat, Launch Octopus before Sting Chameleon, Sting Chameleon's stage will be flooded? Or how beating Storm Eagle before Spark Mandrill will cause electrical outages in the latter's stage? Yeah, shit like that, but everywhere. It can be a minor thing, like an extra power-up that wouldn't have been there before if it wasn't for something the player did/didn't do in a previous stage, or it can be something more impactful, like if the player has to hit a trigger to raise the water level in order to reach a Star Coin, then the next stage, which would otherwise be a fairly standard level, would be filled with shallow water, flying Cheep-Cheeps, etc.
Alright, that's a pretty uninventive example of what I'm talking about, but I'm just spitballing here. Nintendo could definitely come up with loads of inventive ways to change up the stages. It would just require giving the Super Mario Bros. series the same amount of effort as 3D Mario or Zelda. But that would be just stupid. It's only, what, your best selling franchise of all time, right?