@zkat You probably already know about this, but just in case: have you looked at the Game Maker's Toolkit videos? If I recall correctly, there are a few videos that talk specifically about different ways of teaching mechanics to the player (although it's been a while).
My personal interpretation, though this is so far only based in theoretical understanding and adjacent practical experience (UX) rather than practical gamedev experience, is that the mechanics don't have to be simple - they just need to be possible to learn gradually.
So the total complexity of a mechanic may be really high, and it may take a lot of practice and experimentation to figure out how it works, and that's all fine, as long as you don't expect the player to frontload all of it.
Which can be achieved by eg. cutting the mechanic into smaller submechanics and gradually 'tempting' the player into experimenting with permutations of those submechanics through environmental cues and well-placed restrictions and rewards.
(When talking about mechanics that are not strictly required to play the game but that enrich the experience, the "rewards" side of that is probably more relevant than the "restrictions" side)
@zkat As a more personal sidenote, I've personally found a lot of enjoyment in games that are high in total complexity, but where the start is simple, and there's no separate 'learning' phase - you're essentially learning new mechanics throughout the entire game, right up until the ending and sometimes even across multiple games.
Some examples that come to mind would be Dave the Diver and RimWorld, though examples are tricky to come up with, because when it's done well, you don't notice that a game is doing it :)