Magican,
It depended on the patches you used in DLR. Prior to 1.02 it was Thief/Barbarian for their speed. In 1.02 it was Wizard/Summoner for their teleport. After I re-balanced all the heroes around 2001 the Monk became a much more viable hero along with a lot of other heroes that were useless before that.
I understand you aren't looking to create another Paladin clone. The problem is that the Barbarian right now is *right* on the edge of being useful/useless. In some games / maps he's probably going to be the best 1st hero. In others he's definitely not in which case he never gets taken during a game since mid/late game every other hero is better than he is. Taking him 1st is the equivalent of playing a 'rush' strategy since if he doesn't force an early win for you, you're probably toast in the mid/late game.
Recognizing which situations he can be used and not used and dealing with an opponent using him might be the most important first skills you learn as a Warbarons player just as learning to deal with a rush strategy is the most important skill you learn in just about every strategy game.
KGB