Do we really need Choice to pick socks? It is said that you need the Axiom of Choice to pick one sock from each of infinitely many pairs, but that you don't need it for shoes, since you can just pick all the left shoes.

But Choice is equivalent to the statement that every set can be well-ordered, right? And can't be well-order a two-element (or any finite) set without invoking anything related to Choice? If so, doesn't that mean we don't need Choice to pick socks after all?
The axiom of choice is not needed to choose from one pair of socks. You do that every morning when you put on your socks. In fact, even if you have infinitely many socks, choosing one doesn't require the axiom of choice. Neither does choosing five, or ten socks. That's just existential instantiation and induction.

The axiom of choice is needed in order to choose from infinitely many pairs at once. The reason is that between two socks, there is no "left" or "right", and there is no distinguishing property that we can always say that "given a pair of socks, one of them is such and such". And so the axiom of choice is really needed for that.

More formally, Fraenkel, and later Cohen, showed that this argument is mathematically solid. It is consistent that the axiom of choice fails, and there is a set which is the countable union of pairs, but there is no function which chooses a single element from each pair.
Yes you do need the axiom of choice to show that for any set of pairs of socks, there is a choice function that picks one sock from each pair. Each sock from one of those pairs can either function as a left sock or as a right sock so that doesn't give us a way to define in terms of each pair of socks in that set of pairs one sock from that pair. The fact that each pair of socks in that set of pairs can be well ordered is not enough to show that there is a function that assigns to each pair of socks one sock in that pair. To show that such a function exists, you have to assume that the union of all pairs of socks in that set of pairs can be well ordered.

Suppose you have a set of infinitely many pairs of socks. If all those socks were instead shoes and any two socks in a pair were instead a left shoe and a right shoe, then a choice function would exist so how could such a function not exist just because they're socks instead of shoes? That's because to show that the set of pairs of socks has a choice function, you have to assume that that set is a set that can be gotten by turning each shoe in the union of a set of pairs of shoes into a sock and that assumption can't be proven without using the axiom of choice.