You know, it's a sort of a blessing to be SK or reveal NG and start first with Savage Bear or Mangonel. Especially if your opponent does not have Alzur's Thunder or other removal card like that. Now imagine they drop that said Unit with +2 STR and/or a Shield. WTF?
Than you have Decks that is way better for them to play second - Radovid Control with Adepts, for example, cause if you go second you know where to drop this Frost with some Units on this row now, etc, etc.
Also, losing the Coin Flip is really situational. I read somewhere above a suggestion, the guy that starts first to have 1 more extra mulligan for the next round. This actually sounds actually reasonable and it's the best suggestion on the topic that I've seen so far. Will also help the ST Mulligan mechanic and it does, indeed, need a lot of help right now. But will it be fair to the other Factions?
There is no "right" solution here. But to Mulligan a second card between the first two Rounds seems fair to me.