The axiom of countable choice. There seem to be many questions along the same line but none of them seem to be quite what I am asking, so here goes:
If a set is countable, then we know that a bijection exists between it and the natural numbers. Can we then not choose the canonical bijection to be the first one we became aware of? I realize this is not a completely mathematical definition but I have a hard time arguing against it too. Of course this bijection might be different from person to person and from time to time but that shouldn't matter.
 A: There is no good canonical choice. The reason is that for something canonical we need to first have some canonical hierarchy of constructing the universe, and then we need to be able to say within a certain level what is "first" and what is "second".
For example, if $V=L$ is true, then we have such way. Because we can consider the $L$-hierarchy and the definable global well-ordering of $L$ (which is based on that hierarchy). In that case, indeed we can choose the least such bijection.
However, we don't always have that. What we do have is the von Neumann hierarchy, but that doesn't come with a definable well-ordering. And so, for example, when there are countable sets added to the universe, we often "discover" many bijections at once. Not just one. So which one are we going to take? There's no definable choice which "always works out".
The fact is that this is even worse. Even if the set is well-orderable, nay a countable ordinal, there is still no canonical way of choosing a bijection with $\omega$. For example in models where $\omega_1$ is a countable union of countable sets are models where this is true -- there is no way of choosing a canonical enumeration for every countable ordinal. And of course, such models exist (if any models of $\sf ZFC$ exist, that is).
So your suggestion, while reasonable, can only be true in models which have a particular construction, and usually it is such a construction from which we can prove that the axiom of choice is true in that model to begin with.

I should also add that your informal suggestion, and your admittance to this informality "Of course this bijection might be different from person to person and from time to time but that shouldn't matter." is exactly why we try our very best to be as formal as possible in mathematics.
I want that whenever I say $V_{\omega+\omega}$, it doesn't matter who is reading, as long as they understand the definition, they will think about a single concrete object. Otherwise, if everyone is allowed to interpret things according to their own will we have chaos. And you can look back at the historical definition of "function" to see what can happen then.
A: The point of the axiom of countable choice is that if $X$ is countable, i.e. $X = \{x_1,\ldots\}$ and all $x_i$ are non-empty then there exists a function $f$ such that $f(n) \in x_n$ for all $n = \{0,1,\ldots\} = \omega$.
That's not the same as a function which enumerates the elements of $X$, i.e. a function with $g$ with $g(n) = x_n$. In fact, such a function of course always exists if $X$ is countable - that's what $X$ being countable says. (And my sloppy $X = \{x_1,\ldots\}$ notation actually already assumes the existance a such a function - the indexing function $n \to x_n$)
To get from an enumeration of the elements of $X$ (i.e. $g$) to a choice function (i.e. $f$), you have to pick one element from each of the $x_i$, and make it's $f$'s image of $i$. It's exactly this picking that you cannot do without the axiom of (countable) choice. For countable choice, you're only assured that you can pick countably many times, where as full choice assumes that you can pick $\alpha$-many times for every cardinal $\alpha$.
