I think it's totally fine to have Random turns as a game option. I personally would never use this option because after trying it in Warlords 2 I came to a very simple conclusion:
When you move first in the turn you must play very conservatively. When you move second in the turn you must play aggressively.
The reason is a very simple decision tree:
Move First: Best outcome - other player gets 1 move (neutral). Worst outcome - other player gets 2 moves (negative).
Move Second: Best outcome - I get 2 moves (positive). Worst outcome - I get 1 move (neutral).
So it should be clear that when you move first you must be conservative and not leave heroes out in the open or cities empty because the other player may move twice (imagine crows moving 40, Wizards moving 64, Sandworms moving 28 squares on desert maps like Outlands, Serpents moving 60 squares on water etc) allowing him to strike from twice as far away. When you move second you can take risks because you know the worst that can happen is the other player makes his normal move so you can legitimately risk a 60-40 hero battle because your hero may be able to win and then move all the way back to safely if you get the double move and you should definitely send fast units past / toward enemies since you have a 50% chance to rush past them.
The same ideas hold true with regards to buying 2+ production. Always buy it when you are moving 2nd because you have a 50% chance to give the opponent 1 less turn to stop it. But if you buy it when moving first they have a 50% chance to get 1 extra turn to stop it.
Bidding for going first is good in theory, but, in my opinion, is bad in practice.
Experienced players get quite a large advantage over new players. Many new players are likely to greatly overbid for going first.
Also, it would just be annoying to have a bid turn before the first real turn.
There won't be a bid turn. When you join the game it will tell you how much the starting gold will be and you enter a bid at join time.
As for experienced players getting an advantage what's wrong with that? Any one who plans to seriously play Warbarons more than a couple of times will figure out how much to bid and when. Turn order bidding should definitely also be a game option so you don't have to use it if you don't want to.
KGB
P.S. There are 2 annoying things that would happen with random turns: 1 - The battle history will be screwed up because you may have to look back 2 turns worth to see all the attacks against you making it harder for new players to understand what happened because the flashing attack / chat icons only go back 1 turn. 2 - The amount of time you wait between turns will also be randomized so that in a large 8 player game you may go 14 turns between your own turn which could be anywhere between 14-90, yes 90 days.