I vote Agvares. He's always my favorite (2nd place takes Elenhel). Even though his special abilities do not affect most of the units, he's got very versatile slots (another weapon and artifact slot, armor/dress, belt/gloves), that suit pretty much any hero.
Gaudi doesn't have an artifact slot, which is bad for a paladin or a warrior hero, who has only 1 (and some artifacts are well worth using them to boost the things you lack - mana or rage, for example). His ability to improve the crit against undead is nice (practically doubling it), but against vampires, who cannot be critted (because of their special ability), you may find yourself in a battle you cannot win unless you drop your basic crit rate dramatically