One of the most common argued benefits of randomness in games is variety: having some randomness in a game ensures that every match is fresh, or so the argument goes. But you absolutely don't need to wreck the fairness of a game to do this.
Dominion and Prismata are two modern games that have incredible variety by randomizing a single set of units or cards for both players to have access to before the game. After that, there's no randomness in Prismata (Dominion has other randomness and that's a flaw). This keeps the game fair and deterministic while playing but still fresh every time.
It's not even as if Dominion and Prismata are the only or the first widely known games to think of this. It goes back way before Chess960 too; that's a modification of Shuffle Chess which had already existed for 200 years. This isn't even a complicated idea. Rule changes that accomplish the same thing are trivial to come up with for most deterministic games (one I've thought of for Go is having "holes" in the board which act like the edge but are scattered throghout the middle and placed randomly at the start of the game).