Your shoe example is only one part of entanglement.
It is referred as perfect anti correlation - Suppose you and your friend have same shoe size. You take a pair of shoes of your size and randomly send one shoe to your friend. And then you and your friend try the shoe at your respective end. You will always find that if the shoe at your end fit your left foot, then the other shoe will fit your friend in the right foot, and vice versa. This is simple and will happen irrespective of distance between you and your friend and also irrespective of who tries the shoe first. This is simple, not mystery.
Then comes the next part - Statistical correlation - Here is not a correct example, but it should convey the idea. Suppose you and your friend have different shoe size. Now pick numerous pairs of shoes of random sizes and repeat the above experiment. From (say) 100 pairs, some shoes will fit you and some shoes will fit your friend. Say statistically, 20 shows fit you and 30 shoes fit your friend.
It is this statistical correlation (how many shoes fit you and how many fit your friend) that makes the entanglement baffling. The statistical percent is given not by classical math, but by quantum mathematics. And the Quantum mathematics is proven right in all experiments, given sufficiently large number of pairs.
So, no information is transmitted between the pairs, but the quantum particles follow quantum math at statistical levels. By performing variations of experiment, an impression is created as if information is instantaneously (or say at 10K times c) transmitted from one pair to another. That is not true. The real instinctive explanation is yet to be found. There are different views that try to explain the statistical correlation but none satisfies the instinct even though the math is always followed.