Every think discussed here will always depend on the map. Since I play mostly 8 Kingdoms, Battlefield and Tundra I can't care less if heroes fly or not. But I agree with KGB that if you take out his strength, Barbarian has nothing.
KGB wrote:DK Can never be chosen 1st due to being the worst L1 hero of all. Any reason you give for to choosing him 1st, I can show a better hero that can provide everything he does. The DK is purely a hero that gets taken mid/late game when he can start at -6 or -9 chaos and increase that.
KGB
I would like to add an exception on the map "waste". Be cause of the desert map, you really need a few units and everything else can be plundered. And DK gets %70 plunder at level 2, it is pretty high.
I watched a game Razz won on the map waste one on one. He started with DK and keeps plundering and buying scorpions instead. I think it is a viable strategy on this map be cause there are still plenty of room for your second hero HL to reach L4 for 25 leadership. Your goal is to get HL-Sandworm-Scorpions running, add an elephant if possible. Meanwhile your DK keeps plundering and growing for the late game. I adopted the strategy in one game and I think it works.
You can start with a HL and occupy the cities with Giants, Wolf Rider, Heavy Cavalry production and go for a HL-Sandworm-6 meat unit. That is also a viable strategy.
You may start with a Barbarian and send your Barbarian-Sandworm combo directly to your enemy after L3-L4. That should work too.