Like yourself, people aren't surprised by the outcome of your experiment. The surprising thing happens only if you consider more complicated situations. The easiest situations where surprising things happen are these two:
1) Measure the spins of the two entangled particles in three suitably different directions. From the correlations of the observed outcomes you can calculate a number known as the CHSH-correlator S. This number is larger than any model where the individual outcomes were locally predetermined permits. An accessible discussion of this is given in David Mermin's Quantum Mysteries for Anyone. The best discussion of the actual physics I know of is by Travis Norsen in his book Foundations of Quantum Mechanics.
2) Measure the spins of three entangled particles in two suitably different directions. There, you get a certain combination of outcomes which is impossible in any classical model. So you don't need statistics but just a single observation of the classically impossible event. This is discussed in David Mermin's Quantum Mysteries Revistited.
Because it's possible to do things that would be impossible with a hidden local variable theory such as you're describing. See Bell's theorem or https://en.wikipedia.org/wiki/CHSH_inequality, a game at which a quantum strategy can beat any classical strategy.
And see also Sidney Coleman's "Quantum Mechanics In Your Face" lecture (youtube, transcript) which walks through a cousin of Bell's theorem that's I think conceptually simpler—for example, it's a deterministic result, as opposed to a statistical correlation.
There's also a 3blue1brown video on Bell's theorem: https://www.youtube.com/watch?v=zcqZHYo7ONs
The fact is surprising when coupled with the fact that particles do not have a definite spin direction before you measure it. The anti-correlation is maintained non-locally, but the directions are decided by the experiment.
A better example is: take two spheres, send them far away, then make one sphere spin in any orientation that you want. How much would you be surprised to learn that the other sphere spins with the same axis in the opposite directions?
This is the correct answer to the question. Bell and CHSH and all are remarkable but more complicated setups. This - entanglement no matter which basis you'll end up measuring your particle in, not known at the time of state preparation, - is what's salient about the simple 2-particle setup.
I'm not surprised that you're not surprised :D EPR's paper introducing the superluminal entanglement thought experiment was published in 1935, and they basically said what you did - that clearly quantum mechanics was incomplete, and there was some way that the spins had decided which was which beforehand.
Bell's theorem, which uses a significantly more complicated situation to demonstrate why that's not possible, was published in 1964. So it took an entire field about 30 years to see why entanglement should be surprising!
Also, if you want more "surprising" aspects of entanglement, I think superdense coding is a nice example. Basically, sharing an entangled qubit does let you send information, but only after you also send one more qubit in an ordinary way. This is very not possible with hidden variables.
The difference is that spin is a quantum mechanical concept, and this result becomes surprising in light of other things we know about quantum mechanics. Specifically, in quantum mechanics, it's not just that we don't know a particle's properties (like spin) before we measure them, it's that the particle has both properties, it has both spin up and spin down, until we measure it. We know this from things like the double slit experiment, where a single particle goes through two different slits at the same time and then interferes with itself. So when we have these two particles whose spins sum to 0, and we move them far away, and two observers measure their spin at the same time (so that the observers are outside of each others light cones), how do the particles coordinate so that their spins still sum to 0? They both had both spins when they were together, they didn't pick individual spins until the measurement occurred, and yet they still somehow coordinated to have opposite spins, despite being outside each others light cones. That means information must have moved between the particles faster than the speed of light. That violates one of the fundamental premises of special relativity. That is the surprise.
I feel like this is missing something. How do we know they have both spins before we measure them and that they haven't "decided" their spin beforehand?
Because this is how all properties work in quantum mechanics. This was the point of my reference to the double slit experiment, which is the classic example of this idea (called "superposition"). In the double slit experiment, you shoot a particle at a barrier that has two openings in it, and watch where it goes. If you shoot a bunch of particles through at once, then they interact with each other and produce a particular pattern. If you shoot them through one at a time, and they randomly picked one of the two holes to go through, you would expect to see them cluster in two places. This is not what you actually see. What you actually see when you shoot them through one at a time is exactly the same pattern that you saw when you shot them through all at once. Therefor, individual particles actually go through both holes at once and interact with themselves, they are in two different states simultaneously until someone observes them, and forces them to be in one. This is how all quantum mechanical properties work, including spin.
I've read many times about an experiment: take a 2-particle system and measure that it has a spin of 0. This tells us that the particles have opposite spin. Now, take the particles far away from each other and measure one. If you measure spin up, for example, you now know the other particle has spin down.
Why would anybody be surprised by this?
Let's imagine a similar classical experiment that uses literal spin. Take a system of two gyroscopes, each spinning at the same fixed speed, each in it's own sealed box. They can be powered or whatever so they stay spinning for the duration. Stack the two boxes ("entangling" their spin), and measure 0 spin to confirm that the gyroscopes are in fact spinning in opposite directions (some helicopters use this principle for stabilization on the y-axis instead of a tail propeller). Now, send the boxes far apart and measure one of them using the right hand rule. If it turns out to have spin up, the other will intuitively turn out to have spin down. But nobody will be surprised by this because we knew from the beginning that the pair was spinning in opposite directions; we just didn't know which was which before measuring one of them.
------------------------
Update: 2020Apr24
Thanks for all the comments, explanations, and links! I'm not ignoring them, just trying to find time between work and family responsibilities to digest and understand them before I ask my follow-up questions. I appreciate your patience!