Much of mathematics works perfectly well with so-called "naive" set theory. That is, working with sets without worrying too much exactly what sets are. This isn't philosophically that different from calculus courses where you work with real numbers without worrying so much what they are (equivalence classes of Cauchy sequences of rational numbers), or for a more advanced example, modern homotopy theory research which uses $(\infty, n)$-categories without being too bothered by exactly what these are. These are all things that you generally have some intuition for, and until that intuition fails, it's okay to rely on it at first pass.
At some point, students (and mathematicians) need to understand the basics on which the theory is founded, but that isn't necessarily the beginning of their studies. Mathematics isn't just about going down to the foundations and checking that everything is rigorous; you also want to prove theorems once in a while, and sometimes hiding the foundational difficulties until later lets you get things done faster and more intuitively. This is no different from the fact that you weren't taught the Peano axioms of arithmetic in primary school, even though you were learning about the natural numbers. Sure, it wasn't completely rigorous, but finger-counting made it a whole lot easier to prove that $3+4=7$.
The right time to discuss the axiom of choice in any depth seems to me to be at the same point that you begin discussing the other axioms of ZFC and set up an axiomatic foundation of set theory. There's nothing really special about choice; it's an axiom that almost every mathematician is fine with accepting or to whom it doesn't even matter. If you try to talk about the axiom of choice without any discussion of the ZF axioms, you're still using naive set theory, and you aren't avoiding any of the paradoxes that axiomatic set theory was made to circumvent. Giving special privilege to AC isn't any more rigorous than not discussing it at all, just more indecisive.
That isn't to say that mentioning its use in passing does much harm; it may even be overall beneficial to mention such things. The majority of students won't care either way, but there may be a minority who are interested in other foundations besides ZFC, and that minority might be quite interested in the fact that every model of ZF¬C has vector spaces without bases. But spending significant lecture time on it in a course on e.g. linear algebra isn't a good use of the time. Interested students will likely study it on their own (now or later), and the rest of the class doesn't particularly need to know that the existence of bases for arbitrary vector spaces requires choice to prove the spectral theorem or put a matrix in Jordan normal form.
For me, this was in first-year undergraduate courses (and in some cases even in high school). For some other people I know, they didn't learn axiomatic set theory until graduate school. But for what it's worth, those people are now working mathematicians, while I'm a physicist; you can draw your own conclusions on that.