I like the "not too hard" approach. I have a 5 year old daughter and sometimes struggle to find games she can play without getting frustrated because they are too difficult.
The things I find to work best are the ones that have no death or lives mechanics. If you fail you get to try again without any penalty. No spikes, no falling off the ground... A few examples could be Pikuniku or Gris. There are challenging parts in the games, but most of it it's just walking around, enjoying the game.
I honestly hate when games make you start the entire level over when you die. That's probably the reason I've never finished a level of Mario , the fact that each death makes you lose a ton of progress. I love platformer games but when I constantly keep dying and having to start over it really discourages me from continuing to play, so I'm pretty sure I'll go with a checkpoint system where the player only gets sent back to the most recent unlocked cage or found key, i.e. the last actual progress they made in the game.
