I think that air and naval AI will be easier, since the AI will mostly be making decisions about how to allocate forces between regions and between roles. This shouldn't require a lot of spatial reasoning (which IMO is the hardest thing to do in AI) but simpler reasoning about connectivity of strategic regions and relative forces.
I am somewhat hopeful that on land, the battleplan system will help the AI by explicitly breaking the problem into different scales. At the small scale, it has to be able to follow a battle plan, which basically boils down to maintaining or achieving a certain front line. It can be fairly unimaginative about this, just keeping a reasonable distribution of forces along the line and attacking or giving up provinces in a reasonable order and redistributing forces as the situation changes without shuffling them around too much.
At the higher level, the AI has to be able to formulate (and revise!) battle plans. This seems like a harder problem than following a battle plan, but at least at this level it doesn't have to think about exactly how to move individual divisions. One could imagine a bag of possible operational maneuver types where access to each maneuver is scripted to be dependent on having the right forces and force balance. Then it has to choose a set of compatible maneuvers, fit them to the map, and as the plan is executed, periodically evaluate whether the proposed plan still scores well enough compared to alternatives.
There's no particular reason why this division between operational planning and lower-level plan execution couldn't have been implemented in HoI3, but from observation the planning part of the AI, if it existed, seemed fairly rudimentary. I think the design of HoI4 kind of forces this division to be more well-developed.