good games surprise their players.
variance from pseudorandom sources can make a game more skilltesting, fun, and rewarding. it can also do very much the opposite. it is not required or important for fun games at all.
very successful and fun competitive games like the starcraft series and the entire fighting game genre have little to no variance. they are very difficult to master and also fun.
the only pseudorandom effects i can think of in starcraft: broodwar are:
1) starting positions
2) miss chance on units shooting uphill
on a balanced map, #1 doesn't matter that much. #2 typically happens so much that excluding bizarre outliers, the random aspect tends toward not being that significant. i think sc2 even did away with #2 but im not 100% sure on that, i'm sure Jason or someone else that played that game knows.
most fighting games have little to no pseudorandom elements, typically the ones that do exist are character specific. modern fighters have almost none, and the few instances of it are viewed almost entirely negatively and are considered unfun and remove skill-testing elements from the game. the only one i can think of that i've never heard someone dislike is faust's items in guilty gear.
on the other hand, removing variance from magic would almost certainly decrease both the fun and the skilltestingness of the game. skill in magic comes from having to guess what your opponents have, and also around planning for best case/worst case scenarios of what you may be drawing. my experience playing hearthstone (which has no land cards, you just get "land" every turn guaranteed) really felt less intriguing mostly because of the less flexibility in bluffing or whatever inherent in mtg's system
what matters here is the source of the hidden information in the games.
in Starcraft, this is accomplished mostly by fog-of-war. a big part of the skill of the game is figuring out the hidden information based on shown information. "my opponent should have made roughly 500 gas by now, but i've only seen 100 gas worth of units, where's the rest of that spent" and so forth. the complexity of the starcraft resource system is relatively difficult to model in a player's head and requires a strong sense of timing and observation ("how many workers have I seen? how long has he had them? have those workers been mining gas or minerals?"). a system like this is probably impossible to work in a non-electronic game, most hidden game actions on hidden zones don't work very well without a judging party present (the computer in this case). i suppose you could write them all down and then reveal them but that seems quite tedious.
in fighting games, this is accomplished by many of the options being essentially too fast to react to, so in a sense you get rock-paper-scissors except much more complicated and [imo] much more interesting. in rock-paper-scissors, you make a hidden choice and reveal simultaneously. in fighting games you often make choices to do moves that start their effects within a handful of frames (1/60th of a second in most games), which may as well be hidden information until you've actually started to do it. some actions are fast enough to react to if you are looking for them but not if you aren't specifically looking for that subset of options. again this just can't work for a turn-based game.
so in magic, your hand is hidden, and to some degree the contents of your deck is vague. occasionally you have face down exiled cards or morphs, but mostly the hidden information is your hand. have you ever played magic where everyone plays with their hand revealed? it's a lot less interesting. to some degree cards like
thoughtseize negatively affect this aspect of the game, and oversaturating a format with those effects can be negative. but at the same time, you draw again next turn and then there is hidden information back in the mix. and as soon as you have a
brainstorm + shuffle or something similar, the peek effect is almost entirely gone. if you watch good players self-commentate, they always talk about playing around a card the opponent could have or not have, or playing with the possibility of drawing or not drawing whatever card. the variance makes the game much much more interesting. the possibility of non-games because of manaflood and manascrew is a bad awful thing, but i honestly believe nobody has come up with a good solution to the problem.
playing around and with hidden information is very important and difficult in all 3 of these games, and it is a major part of the skills involved. it's also fun.
also, i'm not a fan of chess.