My question is: why is it problematic only when you have to choose?
I mean, what's wrong with choosing a random element from every set? Why do you need a rule?
Where is the "problem"?
If it's only finitely many sets, finitely many choices, people are usually pretty happy with: "Well, choose one, then another, then another, and in a finite amount of time you'll be done, so that's OK."
If it's countably many sets then many people are happy saying: "Well, choose your first one in an hour, then the next one in 1/2 an hour, then the next in 1/4 of an hour, and so on, and after 2 hours you'll have made all your choices, so that's OK."
But with uncountably many sets neither of those works, and so you need an axiom to tell you that this is a permitted operation.
BTW, it's a separate issue, but in your first line, the part in parentheses does not imply, and is not an explanation of, the first part. These statements:
A: The reals are uncountably infinite;
B: There's an infinite number of real numbers between any two random real numbers.
These are largely unconnected. If you think otherwise then you might want to be a bit more careful and precise in your thinking. You might, of course, have simply mis-spoken yourself, in which case it's not a big deal.(To start you off, the second statement is true of the rationals, and of the algebraics, both of which are countable).
I could understand the objection if one objected to the concept of infinity in the first place. Like "infinity is not real therefore any logical statement you make about it is non-sense".
What I don't understand is the mindset that would accept to be presented with an infinite number of sets but then not accept that you can choose an element from each set, because "the procedure will never be done" or something like that.
Similarly defining an infinite collection of sets.
However, if I have an uncountable collection of non-empty sets, sometimes you can tell me how to choose one from each (for example, if I have uncountably many pairs of shoes then you can just say "pick the left one"), but within the axioms of set theory, if all you know is that there are infinitely many non-empty sets, the ZF axioms don't allow you to declare that there is a function which when given one of the sets, returns to you an element from that set.
Your statements seem to be saying "If you accept that there are infinite sets then you must accept that the Axiom of Choice is 'True'."
That turns out not to be the case. There are sets of axioms that result in systems that have infinite sets but in which the Axiom of Choice is not 'True'.
Perhaps I've mis-characterised your position.
There are infinitely many families.
Now suppose that there is a council meeting, and every family needs to send one representative. To do so you need to choose one number from each family, and it's not clear how to do that. I invite you to try to think of a rule that works for all families.
So to choose one number from each family we need the Axiom of Choice.