In both examples you are given an infinite family of sets of size 2, and a choice function picks an element of each family. In the case of the sets of shoes, each set comes with an ordering (left, right), and so we can define a choice function explicitly. In the case of pairs of socks, this is not the case: Of course, given any pair, we can assign an ordering to it so we can select one of the two socks. However, there is no obvious way of uniformly doing this for all pairs at the same time. This means (at least intuitively) that there is no way of defining a choice function. Its existence can only be granted by applying the axiom of choice.
There are several variants of this example. One that may be useful to think about is the following: One can show explicitly that if $A_n$ is a set of reals and $|A_n|=2$ for each $n\in{\mathbb N}$, then $\bigcup_n A_n$ is a (finite or infinite) countable set. However, it is consistent with the axioms of set theory except choice that there is a sequence $(A_n\mid n\in{\mathbb N})$ of sets, each $|A_n|=2$, and yet $\bigcup_n A_n$ is not countable. Although the construction of the model where this happens is technical, the point is that this formalizes the intuition that there is no "explicit" way of choosing a sock from each pair, simultaneously, and that any way of doing so is essentially non-constructive.
For more on the set theoretic versions of these collections of socks (Russell cardinals), see here.
A common definition of function between two sets (or between two classes, when working in GBN) is based on the notion of "ordered pair". An ordered pair is some set-theoretic construction, denoted "$(a,b)$" where $a$ and $b$ are sets, with the property that
$(a,b)=(c,d)$ if and only if $a=c$ and $b=d$. There are many ways of achieving this; the most common is the Kuratowski definition of ordered pair:
Definition. If $a$ and $b$ are sets, then the ordered pair $(a,b)$ is the set
$$(a,b) = \Bigl\{ \{a\}, \{a,b\}\Bigr\}.$$
Note that $(a,b)$ is a set if $a$ and $b$ are sets. The Axiom of Pairing guarantees the existence of a set $P$ that contains $a$ and $b$ as elements; and then both $\{a\}$ and $\{a,b\}$ are elements of the power set of $P$, so $(a,b)$ is an element of the power set of the power set of $P$. Also:
Theorem. $(a,b) = (c,d)$ if and only if $a=c$ and $b=d$.
Proof. If $a=c$ and $b=d$, then $(a,b)=(c,d)$. Assume now that $(a,b)=(c,d)$. Then
$$\{a\} = \cap(a,b) = \cap(c,d) = \{c\},$$
so $a=c$. If $b=a$, then $(c,d) = (a,b) = \{\{a\}\}$, so $\{c,d\}=\{a\}$, hence $d=a=b=c$. Likewise, if $d=c$, then $a=b=c=d$.
If $a\neq b$ and $c\neq d$, then $\{b\} = \cup(a,b) - \cap(a,b) = \cup(c,d)-\cap(c,d) = \{d\}$, so $b=d$. QED
Now let $A$ and $B$ be sets (classes if you are in GBN). The cartesian product $A\times B$ of $A$ and $B$ is defined to be
$$A\times B = \{ (a,b) \mid a\in A, b\in B\}.$$
If $A$ and $B$ are sets, then so is $A\times B$: it is an element of $\mathcal{P}(\mathcal{P}(\mathcal{P}(A\cup B)))$.
Now we are ready:
Definition. Let $A$ and $B$ be sets (or classes). A function $f\colon A\to B$ is a subset (or subclass) $f\subseteq A\times B$ such that:
- For all $a\in A$ there exists $b\in B$ such that $(a,b)\in f$; and
- For all $a\in A$ and $b,b'\in B$, if $(a,b)\in f$ and $(a,b')\in f$, then $b=b'$.
The idea is that $f$ "assigns" $a\in A$ to $b\in B$ if and only if $(a,b)\in f$. In that case, we write $f(a)=b$ (to mean $(a,b)\in f$).
The problem with your last bullet point is really the first bullet point. You seem to be confusing "function" with "function you can name".
The problem with the Axiom of Choice is more subtle than the notion of "being able to write down something". For example, if you restrict your universe to the "constructible sets" (see Wikipedia's article) of ZF (without assuming AC), then the Axiom of Choice is true for the constructible sets.
Best Answer
Given a finite number of nonempty sets $A_1,\ldots,A_k$, the Axiom of Choice is not needed to show that there are functions $f\colon\{1,\ldots,k\}\to\cup A_i$ such that $f(i)\in A_i$ for each $i$. That is, there is no need for the Axiom of Choice in order to select an element form finitely many nonempty sets.
In particular, you do not need the Axiom of Choice to show that you can choose a real number (a single set).
Simply: since $A_1$ is nonempty, there exists $a_1\in A_1$. Since $A_2$ is nonempty, there exists $a_2\in A_2$. Likewise, we have $a_i\in A_i$, $i=3,\ldots, k$. And we can let $f=\{(i,a_i)\mid i=1,\ldots,k\}$ be the Choice function.
We can write all of this down because there are finitely many $A_i$.Apparently there are subtle non-standard-set-theory issues here (thanks to Carl Mummert for the pointer); so instead, let's say that for a family of nonempty sets indexed by a natural number you do not need the Axiom of Choice to get a choice function, and this can be shown by induction on the index set.The specter of the Axiom of Choice (so to speak) does not even begin to suggest itself until you have to make infinitely many choices. Even then, you may not need it.
Note, however, that using phrases like "arbitrary real number" may make it seem like you are talking about some kind of uniform probability distribution over all the real numbers that makes all "selections" equally likely. This is a completely different thing altogether, but not what you are talking about here. This is likewise the problem that arises when, in the context of probability, we talk about "selecting a random integer." The problem with "selecting a random integer" is that you cannot have a uniform probability distribution on the integers: this would amount to a measure on the power set of the integers that is $\sigma$-additive, for which each integer has equal probability, and for which $\mu(\mathbb{Z})=1$; no such thing exists, because you would need to have $\mu(n)=0$ for each integer $n$, and $\sigma$-additivity would imply $\mu(\mathbb{Z}) = 0$ as well. This is what is behind the statement "you cannot 'choose a random integer'" true in that context; but this is an obstacle in the notion of "randomness", not a set-theoretic obstacle. Likewise, there can be no uniform probability distribution over all the reals, because uniformity would imply that each interval $[n,n+1)$ with $n\in\mathbb{Z}$ would have the same measure, and $\sigma$-additivity together with the fact that the reals have finite total measure implies that each interval must have measure equal to $0$, and so the reals would also have total measure $0$. Again, this is a probability/measure-theoretic obstacle, not an Axiom-of-Choice one.