What makes quantum-entanglement communication so surprising? I don't understand why quantum entanglement seems so surprising to physicists in the case of communication. 
Let us say we take a pair of shoes, and put the two shoes in two separate boxes, and shoot one of the box into a black hole while holding the other box at the other end of the universe. If I were to open the box inside the black hole and find the left shoe in it, it is obvious that the other shoe in the far end of the universe will be a right shoe. The two objects are pre-entangled pairs, there is no need of further communication to maintain their entanglement. 
 A: I like to teach undergraduates about what new mathematics you can do with entanglement, with a game that I like to call "Betrayal."
Rules of Betrayal
Betrayal is a cooperative game for a team of 3 people. They are playing against and trying to beat the game. The game is usually going to force one member of this team to act at cross-purposes to the other two; I will call this person the "traitor" for short. (Of course since they're cooperating with the others they don't want to betray their friends!)
The whole game consists of some large number $N$ of similar rounds. The team is allowed to prepare however they want between each of these rounds.
In each round, all three teammates are put into boxes through which no known communication can travel.1 They can bring whatever they want to into that box. Each box has a timer, a screen onto which the game will display a message, and two buttons marked $0$ and $1$. After we display the message on the screen, the timer counts 5 minutes which they have to press exactly one button once, locking in their numbers. We then bring everyone back together and sum up these three numbers, and they win based on whether the sum is even or odd. Tampering with the box in any way other than pressing one button once during a round is, of course, against the rules.
Getting more in-depth, 25% of our tests are control rounds. We display on all three of their screens, "Make the sum of your three numbers even." When we get back their chosen numbers and sum them together, the team beats that round only if this sum is even. Simple enough, right?
In 75% of our rounds we randomly choose one of the teammates to be the traitor, and we lie to them by broadcasting that same message onto their screen: "Make the sum of your three numbers even." As for the other two, we broadcast the true objective onto their screen: "Make the sum of your three numbers odd." When we get back their chosen numbers and sum them together, the team beats that round only if this sum is odd. Everybody is, of course, informed in advance about these rules.
Now in this hypothetical future, the team plays this for something like 3-4 weeks straight, doing 300 rounds total, and they win if they beat 270 or more of these rounds. To give some financial incentive, let's say the team gets to split a trillion credits if they win, but they have to pay ten thousand credits if they lose, where a credit in the future is equal to the present value of a dollar.
(Footnote 1. Technically, this is achieved by those boxes being inside of spaceships which fly until they're more than 5 light-minutes apart from each other, but that's not super-important.)
Classical limits
It turns out in classical probability the above game is exactly identical to a slightly revised game: we similarly separate the players and then we ask all of the players "what would you do if you told us to make the sum even?" and they press one button; then we ask all of them "what would you do if you told us to make the sum odd?". Doing so we get 6 total answers, of course. Let's call our players Alice, Bob, and Carol and denote their answers to the question $(A,B,C)_{o,e}$ where $A_e$ is "Alice's answer if we ask her to help make the sum even."
After this process we choose, uniformly at random, to either evaluate $A_e + B_e + C_e$ for evenness, or $A_o + B_o + C_e$ for oddness, or $A_o+B_e+C_o$ for oddness, or $A_e+B_o+C_o$ for oddness. Note that at least one of these cannot hold, because summing all three together we would find that $2(A_e + B_e + C_e + A_o + B_o + C_o)$ is even+odd+odd+odd = odd, but two times anything is even. You can only satisfy at most three of these at once, which means that your best strategy will always fail 25% of the time. Invoking the binomial CDF we find out that your chance of getting 30 or fewer failures on 300 trials with a failure probability of 25% is 0.0000000000412,  or one in 24.3 billion. So at that rate you would have to spend something like 243 trillion before you could expect to win 1 trillion. I was going to say that the administrators of the game would therefore be very happy, but with on average 120 trials before each failure the $10,000 probably does not cover their personnel costs to administer the game for the necessary weeks...
Quantum limits
If these three people share a quantum-entangled state of three qubits, their chance of failure is 0%. To see this, define $|+\rangle = |0\rangle + |1\rangle$ and $|-\rangle = |0\rangle - |1\rangle.$ The state $|+++\rangle + |---\rangle$ only has even sums (in the qubits' computational basis) in it: "make the sum of your numbers even," check. Just don't modify the state, and measure it.
The state $|+++\rangle - |---\rangle$ has only odd terms. Any two people can transform the former into the latter by the unitary mapping $|+\rangle \mapsto |+\rangle,$ and $|-\rangle \mapsto i|-\rangle,$  and then whatever they measure is odd.
However, quantum entanglement, to be preserved, needs to be isolated from the world around it. Basically, if an entangled qubit interacts with its environment in different ways for its $|0\rangle$ and $|1\rangle$ states, then this interaction causes the environment itself to now be entangled with the qubit, and in practice that means that no qubit is 100% faithful. But if each qubit has roughly a 3% error over the course of the experiment and we naïvely sum that to a 9% error for the whole ensemble, we get a 76.4% chance of passing all of the trials, which is pretty darn good; we'll probably get it the first try and we'll almost definitely get it in the first 4.
