I think the foremost reason for the game feeling too easy now is foresight. Either from having played the game before, or from getting tips online. I don't know how the advantage of foresight can be negated, but more randomness could be a part of the solution.
Exactly. Knowing the twist the AI has in store for any given fight makes the fight much easier. Rehearsals make for great videos.
