A great example is Diplomacy[0]. Instead of randomness, you have asymmetrical information, for which you have to use the same type of statistical reasoning. This is much more satisfying than randomness, because there is substance behind the veil.
There are 7 players, and each starts with 3 or 4 units. The outcome of an attack is determined entirely by numerical superiority. If you attack with more units than are defending, you win. However, because there are so many more players than units, and all orders for a turn are resolved at the same time, you don't know what's going to happen because you don't know what other players are going to do. Will your allies actually support your attacks, or will they backstab you and defend your opponent instead? People can make your attack or defense fail simply by not writing the order to support you, because you don't have enough units to do it alone. Therefore, the outcome is dominated by cooperation between players. You don't know what will happen only because you don't know who's lying.
And this gives you a way to overcome the "random" element by finding out who's really lying using... Diplomacy!
Mafia is another game that relies on asymmetrical information instead of randomness, if you forgive the fact that roles are randomly assigned. This is a less pure example, because there is some element of randomness. However, the information game is still more important, because the randomness is limited to setting up the board. Poker uses this kind of randomness, because once you shuffle the deck, the result of drawing a card is not random. Procedural generation is a mixed case, but I think it usually falls into this bucket as well.
In general, randomness is good when it is used to hide information, but it can become very frustrating when it is used to create information independent of any other causal structure. Randomness is bad when it destroys the narrative a player is forming about their experience. If the causal structure of your game is capable of hiding information without relying on randomness, like with Diplomacy, then you don't need any.