I find the heroes to be highly situational. Dreadlord is often a good choice in the absence of allies or if you choose to accept elementals/medusas, but that's about it. I generally choose Valkerie if I buy fast-moving allies, and Paladin if I expect the opportunity to capitalize on XP.
I find that Paladins tend to quickly become the prominent hero because of their XP gain. Level~10 is just better than level~7. Etc.
I chose Valkerie recently to grab up the large number of accessible ruins on one map. I chose it again on another to keep up with the two Demons she came with, and search distant ruins and look for backdoors to the enemy. I was successful in both tactics.
Dreadlord is very useful in certain circumstances. But he quickly loses his advantage when +stack allies enter the field or enemy heroes with better movement get the drop on him. He can't afford not to strike first. Then again, that's his advantage. I lost my position in one of those games because I had to attack the enemy Dreadlord with a 60% chance of victory, or defend from him the next turn with a 20% chance (he was also being reinforced). I lost the battle, boosting his hero's level, and I didn't manage to kill the guy off until today. Now I'm sitting on 6 cities instead of 11, practically out of the game