It's a little bit feelbad for one player to have the unfair advantage of going first, but someone has to go first.
Assuming you're interested in your depth:complexity ratio, you should seriously consider not mitigating the first-player advantage. The objective of mitigating first-player advantage is to improve the game. Adding unnecessary complexity or strange rules, is often not worthwhile.
How big is the advantage? In a game with many small turns, it's probably not worth worrying about. In a game with fewer turns, where the turns are significant, it's a bigger problem.
In a two-player game, the second player will get one less turn in half of all games. So, on average, they're getting half a turn less. You compensate for this, by making the first turn a half-value turn, or by giving the second player an extra half a turn worth of goodies. In a game with more players, the last player should get compensation almost equal to a turn.
The ideal place to apply mitigation is inside the game components themselves, because it's invisible, and adds no complexity.
In Scrabble, there's no special rule for going first, it's just that there aren't many premium squares you can reach on the first turn.
For most games, however, the solution is simple. You find the most basic game resource, and dole it out in differing amounts, based on the player order.
In Lords of Waterdeep, the player going first begins the game with 4 coins, the second player 5 coins, the third player 6, etc.
In Star Realms, players draw a new hand of five cards each turn. To mitigate the first-player advantage, the player who goes first gets a hand of only three cards on their first turn. It's like a mini-turn. Perfect.
My gangster game had two resources: Health and Money. Everyone started with ten health, and some small amount of money. I gave the players, in turn order, 1/2/3/4/5 money tokens, to begin the game. However, this was too much, and 4 or 5 money tokens allowed the later players access to very powerful effects. A turn is only worth about three money tokens. In the end, I settled on a 0/1/1/2/2 system. Slightly more complicated, but still very a fairly simple solution.
However, players 3 and 5 are disadvantaged by this system, as they get the
same amount of money as the player who goes before them. So, how about if players three and five got some Health instead of some or all of their money?
I could make a combination that's very fair.
This goes too far. Having 11
or 12 Health at the start of the game might be fair, but it makes the strategy
of the game different, based on your seating position. It's also rather odd, and
is not easily remembered. A player would have to refer to a chart each game. It's not worthwhile.
You should not create something that has an ongoing effect, or that warps the game in some way. I'm not a fan of the "keep going until everyone's had equal turns" rule. That means the effect of going first is something that will persist to the end of the game, and matter again. Fair, yes. Wonky, yes also.
In round-based games, it's fine for the starting player to change from round to round. This is a very simple and interesting choice you can add to a player's options for their turn. If it doesn't fit in, you can just have a starting player marker move clockwise around the table each round.
Don't use completely variable turn order, where play doesn't go around the table in a circle. This is usually accompanied by this turn order changing every round. This is an annoying and time-consuming mechanic, and people will constantly be getting it wrong, and forgetting that it's their turn. As always, if the game is about the varying turn order, it's perfectly acceptable (Kingdomino, Power Grid.)
This problem is not an opportunity to stuff in extra flair and complexity. First player advantage is a problem that should be solved with the most unobtrusive solution that works — or not at all.