The concept of +25 leadership as a cap is a bit hard to contain, but where does a reduction leave the Horse Lord as a hero? He's situationally useful at best for the moment; will he really even be that much if he's nerfed? He's good for a support hero, no doubt. Maybe his +leadership could be spread out over more levels, 5 points per purchase, so that players would have good reason to purchase his other great attributes like group move? I'd still want to see him cap at +25 so that he won't be a flavored-but-useless hero. Again, we're talking about a bonus that is useless in cities and even when maxed is only applicable to one terrain type. His real threat is as a support unit; a walking tower.
He tends to rule certain maps, especially those with few significant terrain features and choke points. He does not tend to be a generally useful hero. Is it time to consider restricting use of certain heroes on certain maps?