I don't think the Chess example showed randomness at all, on further inspection.
I think the important point is that the player makes a choice; the player may not understand the consequences of his actions, but the player still definitively made a choice, and that choice was not random (the fact that the player fails to understand the factors determining the choice does not mean the choice was not deterministic).
One of the important things to know about humans is that, even (especially) when trying to be random, they fail miserably at it. Choosing "at random" from a set of multiple seemingly viable options does not make the decision random, no matter how hard the player tried to do so.
The bit about "who you are" and "who your opponent is" somewhat fails too. The tournament structure may have randomness in it, but the game itself does not. Even if you claim you have a "rock" player and a "paper" player, if a "rock" player were capable of playing a "scissors" game from a similar set of opening moves, then such a player would be favored tremendously. This fanciful "rock/scissors" player would have an advantage over both paper and scissors players.
As for the library being random, I say no it is not (the order is, but the contents are not). My library never contains a
Chimney Imp unless I actually want to play with it. At best, it contains nothing but friends whom I enjoy doing different things with, and whenever I draw a card and say to myself "Oh I wish I hadn't drawn that", there is a simple solution: take the card out of the deck. Suddenly, the chance of me drawing the card are 0, and I am happy.
This fits in quite contrary to your claim that "the library is random". I have a "cycling" deck which contains nearly 30 land. Why do I like it at all? Because it is never, ever mana screwed. I could hypothetically be screwed, somehow, but having ~30 land plus eight land cycling cards tends to "un-randomize" that deck.
Furthermore, I have tremendous control over my decks. The fact that they are, like children, a little beyond my perfect control, doesn't bother me quite so much. Unlike children, I can willfully rip out any part of them and replace it however I like, with no consequences (trying this with children will at best lead to awkward questions).
I have to concede that the order in a Magic deck is a bit random. I wonder if one of the reasons I like weenie decks so much is that every card in my opening hand is one for the opening game?
Lastly, and I think you said this in your article, but what makes the game fun isn't the randomness, but the player's actions. One of the things I disliked about Cosmic Encounter (which I tried playing because it inspired a lot of the things in Magic) was how little control I actually had over myself.
Maybe the struggle is finding the randomness players are/were willing to accept, while cutting out the parts they are not.
P.S. I had a friend who delighted in Starcraft but refused to play Warcraft III because the damage in Warcraft III is random. Funny but true (though I think the variability could potentially be too high at times).