If you split up an entangled pair of particles and measure them in a the same 50/50 basis simultaneously (sort of like a coin flip) at distantly removed places, the results will be individually random but perfectly correlated when compared with each other. It seems natural to assume that something here was pre-determined. i.e. There's was some kind of hidden information that we haven't found a way to measure yet. The way in which the coin-tosses were going to pan out was determined when the pair of particles were entangled.

Quantum physics makes predictions that suggest this isn't so. You can design experiments (e.g. A Bell inequality test) in which quantum physics predicts correlations that go beyond what would be possible with some hidden local information attached to the entangled particles that we just don't know about. Experiments don't prove theories to be correct. That's not how science works. However, experimental tests of Bell inequalities have pretty conclusively shown that local hidden variable theories are inadequate to explain what's going on.

Yes, it appears what Einstein called "spooky action at a distance" seems to propagate close to instantly. It's important to appreciate that you can't transmit information this way though. We can only make sense of the quantum correlations after communicating other information at classical speeds. Sometimes you see quantum entanglement devices allowing FTL communication in sci-fi, but that's pure horse hockey.

That all being said, I don't understand quantum physics either.