I played a few games and I lost most of them. From what I saw, there are several interesting hero duo's. Here is my favorite, I call them:
FAST AND FURIOUS, Horse Lord with Valkyrie.
Advantages: Valkyrie gives you attacking leadership bonus and Horse Paladin gives you land leadership bonus.
Strategies: Early in the game use Light-Heavy Cavalry, Wolf Rider, Giants and even light infantry, anything with 15-16 moves or more. Mid game you can get an Elephant or Mammoth for further move bonus and land moral bonus and use them with Battering Ram and Yeti. Later in the game get few units from your standard heavy hitters Great Archon-Devil-Red Dragon-Green Dragon based on your opponents strategy. Also train Wizard near the center since he is the only one who can catch up with your hero stack and replace your occasional losses. Barbarian is always welcome and he levels up faster here than running solo. Stay away from Catapult, Element, Medusa, Spider even Gryphon for your hero stack since they will eventually slow you down.
Beware: Flyers may slow you down on the roads since it takes them 2 moves to go one unit for them where for the landers it takes 1 move to move 1 unit. If you have flyers on your hero stack, you may need to move them separately. But be careful and calculate the moves carefully. You don't want to end up splitting your hero stack.
Drawback 1: You will loose the hero battle to the Assassin, but there is no way he can catch up with you unless you are not careful. If your opponent is using ambushers you can add Mammoth, Yetis, Ghost or Ranger for further protection.
Drawback 2: This doesn't work on the hills and it doesn't work on the path through the hills, so be careful where your hero stack ends up. You are safer on the outside if you stay on the green. The only way you can be safe in the cities is with Great Archon (against enemy leadership) and Devil (against enemy morale) .
Drawback 3: Probably not the best duo for a small map where there is a chance of early encounter with a well developed Barbarian, Assassin or Paladin.
What is your favorite Hero Duo and what is your strategy?