From personal experience I can wholeheartedly recommend these games as I played them with my four year old son and he, even after a year, still remembers them fondly and often talks about them...
1.
Abzu
It's atmospheric exploration game about reviving ancient waterworld.. You control extraterrestrial diver swimming through primeval sea, gathering information about marine life and learning about submerged civilization whose remnants he encounters along the way... In subtle way, without extensive infodumps and through environmental gameplay, it relates itself with Sumerian and Babylonian creation myths. My son is fascinated by water creatures, prehistoric and contemporary, since he grew up watching
Jeremy Wade's River monsters (I've been planning to take him fishing with my friends for a while now and to buy him Ultimate Fishing Simulator), so it was really nice to watch as he enthusiastically recognized different species... We took a lot of screenshots also, as the gameworld is gorgeous.
2.
Gorogoa
It's a nice, short puzzler more in line with the capabilities of five-year-olds than your examples of The Witness and Talos principle (if I wasn't in a friendly mood I would say you're full of it, but I won't
).. Wholesome, contemplative experience with a picture book visuals, its gimmick is based on rearrangement and manipulation of parts of the images. Modest point and click affair but since it was his first in the genre, I sympathized with his infatuation with it. On several occasions we had to seek help from walkthroughs, but that's because I suck at these types of games...
3.
Hidden folks
Hidden object game, with DIY aesthetics... I love the sounds which developers made by themselves. We spent a lot of time on it, and have it installed on my android phone. Even my wife who opposes the notion of raising a child to be a gamür enjoyed it... That's saying a lot, believe me
I can also recommend old Disney platformers, such as Aladdin, The Lion King, and The Jungle Book coupled with watching them off course.. Better than this grooming shit the studio produces today. Happy gaming dad who sacrifices free time to play with his children!