Great article all around. Too many game designers forget that us gamers feel cheated when the computer pulls a dick move like shooting us in the head with a pistol from across the map or the well-known Mario Kart trick of warping the computer players up behind us even when we left them in our dust.
I don't know if "social contract" is the right phrase, though. I think "expectation" might be a better way of describing it. (Maybe they are the same thing?)
All of the expectations you mentioned are spot on. We expect the enemy, even if computer controlled, to be approximately as capable as us. They should be under the same limitations, including line of sight, steadiness, and reaction time. Anything less makes them uninteresting, anything more makes them unfair. Same thing for the boss fights: if a boss has 10 times as much health and multiple weapons, he had better have some sort of weak spot to make up for it. If not, how is the player ever supposed to win? An unbeatable game isn't fun at all: we expect that we are able to win with enough cunning and practice, otherwise there's no point to playing.
Randomness is also a huge one and one that drives me crazy. Dying due to random chance is terribly frustrating, because you've been punished for something that you couldn't control. Equally, winning due to random chance kills any sort of sense of achievement, because you know that it wasn't your own efforts that lead to the win. Randomness is good for keeping things different and for adding some dithering to a conflict so that even the underdog wins sometimes, but when it overshadows skill, you're not playing a game, you're playing a lottery.
The other expectation you mention is the tendency to improve in strength over time. I'm not sure that this is an expectation of games so much as an expectation of learning: we naturally measure our progression in terms of how much easier our past challenges become. If the same enemies are still just as difficult 10 hours later, I don't feel like I've improved; I can't immediately tell that the enemies have improved along with me. Without that yard stick to measure our progress against, we lose the reward mechanism that comes with learning a game.
One case you didn't mention is the pre-scripted death or escape. It's really disappointing to give it your all in a fight and lose, only to find out you were supposed to lose and never could have won. If I couldn't win, why was I trying? How do I know if I can win the next fight? It's cheating in the purest sense and it undermines the trust that gamers have that a game is beatable and therefore worth playing. Almost is bad is when you beat the bad guy, only for him to fly away. You worked so hard -- you won -- and yet you are denied the gratification. It's like playing a board game with somebody, and when you win, they tip the board over and say, "Nope, didn't happen, nobody won."
Gamers play games because they are challenges to be overcome. If there is no practical way to overcome them, then they aren't worth playing. Vice versa, if there is no challenge to overcome, they aren't worth playing. "Hard fun" is a delicate balance between the two where the challenge is one we know we can overcome, but it's going to take some effort.