I agree that as far as the campaign goes, M is the best. The AI does not make better choices, field better armies or get any financial boost from the VH setting, they're just insane, which you can perfectly emulate in M by attacking everyone yourself

On Medium on the other hand, you can expect a modicum of respect for diplomacy and alliances, even though some weird stuff still happens (for instance, as the HRE I managed to ally with the Poles and Danes (married the Danish princess, and had the Polish heir marry mine) while I was sieging both Hamburg and Magdeburg. Both the Poles and Danes at the time had large armies waiting around for me to assault and fail or to be beaten back somehow, waiting for their turn to siege in other words. When I finally got the castles, these armies seemed "trapped" in my lands : they wouldn't move, wouldn't attack brigands, wouldn't attack me either. Just sat there, and occasionaly helped me whenever I attacked brigands in their control zone. *shrug*).

On the battlefield, the AI definitely is more of a challenge on VH, even though it still has an issue with keeping a battleline : the AI units seem to always go for the best odds for them at a given time, without much of an overarching strategy behind them all. But that doesn't make them any less lethal, and I certainly suffer much, much more costly victories as I did in Rome.