Now that turns are determined by who took action last I had an idea to determine who goes first.

Use a variable to determine if a player went first last game. That way, when the next game is started, both players will have a variable that says if they went first last game.

If Player 1 went second last game, and Player 2 went first, then it would recognize that and allow Player 1 to go first. That way, everyone should get equal chances to go first. If both people have the same value (No/Yes) it would be done at random like it currently is.

I just hear people complaining about never going first, which has never really bothered me, but this would even the distribution out.

Actually people was complaining about not going first in round, not in game (at least I never seen person complaining about 1st action in game). But I agree that with new first action system going first at start of game can give player more chances to go first in further rounds.
From the other hand going first is not always good, and at start of game it is bad: for example enemy doing actions after you so he can select what card to cast against creatures you created, while you know nothing about his possible creatures when casting yours.

I agree with Altren. Now that the system for each turn is fixed, it doesn't really matter that much who goes first at the beginning of the game. As he says, sometimes it can be a bad thing to go first early on.

I often find that on rounds 2 and 3, after casting some kind of scout, and knowing that my opponent has, say, a hell cat, or windreader in play, I have to play more conservatively than my opponent, knowing that he will get a chance to react to whatever I do.