Yeah, imho it is the depth that I think is the biggest hurtle to overcome - mainly because there is apparently no shallow end to the pool.
I wonder if Das is still playing it too skillfully - he obviously deeply understands the units he is playing with. Like if instead there is a way to brute force the game, just building crossbowman and pikemen, with the pretender or a commander, maybe adding a bonus to the Human player or disadvantage to the AI player, just so the beginner could learn the mechanics of the game. Perhaps ignoring formations, spell dependency, maybe a map without an AI only neutrals, etc. I don’t know. There should be a simpler way to present a first play through. For example, it isn’t until a couple of turns in we learn taking thrones is good.
EDIT: You mentioned a MOBA - yet those draw you in because almost everything happens for you. Yet there is depth in the characters, how they fight/defend, and what weapons and such they can buy that you learn later. Admittedly it is much flatter than something like Dom, but still that shallow end reduces the fear of getting in.