This question is quite subjective, but here goes:
The axiom of choice notoriously leads to many extremely counterintuitive results, like the Hausdorff, Von Neumann, and (most famously) Banach-Tarski paradoxes. Unfortunately, the proof of these paradoxes is also notoriously complicated, and it's not at all obvious why an axiom as seemingly innocuous (and, in fact, obvious) as the axiom of choice has such strange consequences.
Do there exist any examples of a simple chain of reasoning that leads from the axiom of choice to a counterintuitive result? (Though not necessarily a result as spectacularly counterintuitive as the Banach-Tarski paradox.) One which is simple enough that someone without training in advanced mathematics could understand the general train of logic (with perhaps a few steps fudged over)? I've never see an example that lets me intuitively understand why naive intuition "goes wrong" exactly at the step where we use the axiom of choice.
(To be clear: I'm not looking for a simple counterintuitive result that follows from the axiom of choice - Banach-Tarksi would qualify for that. I'm instead looking for a counterintuitive result that follows from the axiom of choice with a (relatively) simple proof.)
Intuitive and counterintuitive results are tricky, as you said, it's a subjective thing.
Let me try and give you one example, a discontinuous solution to Cauchy's functional equation. Namely, a function $f\colon\Bbb{R\to R}$ satisfying $f(x+y)=f(x)+f(y)$.
It's not hard to see that such function is necessarily $\Bbb Q$-linear, so start with a Hamel basis for $\Bbb R$ over $\Bbb Q$, now pick any permutation of the basis, and extend it to a linear automorphism. Since you switched two basis elements, you didn't get a scalar multiplication, so you got a function which is not continuous or even measurable.
The last sentence also show that choice is necessary, since it is consistent with the failure of choice that all $\Bbb Q$-linear functions are measurable, which implies they are continuous, which implies they are scalar multiplications.
There are two issues here: the axiom of choice allows us to go "outside the structure", and infinite sets are weird.
Outside the structure?
One of the arguments about choice not being constructive is that the axiom of choice does not tell you how to obtain a choice function, it just tells you that such function exists. But because we are not limited to a specific construction, or constraints, or anything, this function does not have to obey any rules whatsoever.
From a more category-centered view, you can show that the axiom of choice does not hold for $\bf Ab$ or $\bf Grp$, because not every epimorphism splits in these categories (case in point, $\Bbb R\to\Bbb{R/Q}$).
But set theory doesn't care. Set theory ignores structure. There is a function, and its range is a set, and we have to deal with the fact that this might be counterintuitive and lead to things like the Banach–Tarski paradox or a Vitali set existing, because once you have a set (of representatives), the rest is just stuff you can do by hand.
So we get that the axiom of choice, by letting us split surjections, creates sets which sort counter our understanding of a given "structure". But of course, this is not the fault of the axiom of choice. This is our fault, for not understanding the interactions (or lack thereof) between "structure" and "sets" in general.
Infinite sets are weiiiiirrrrrdddd!
The second reason for many of the paradoxes is that infinite sets are weird. Look at the free group with two generators, $F_2$. Would you have expected it to have a subgroup which is generated by three generators? By infinitely many? No, that makes no sense. And yet, this is true. $F_2$ has a copy of $F_\infty$, and thus of $F_n$ for all $n$.
Or, for example, would you expect $\Bbb Q$ to be homeomorphic to $\Bbb Q^2$? That's also weird.
But these things don't even have to do with the axiom of choice. They have to do with the fact that we are finite, and these sets are not. And we base our naive intuition off finite sets, and then it fails. So we fix it, but we still base our intuition off of sets which "we hoped were good enough" (hence the ubiquity of the terms "regular" and "normal"), but these too fail us.
What's really funny is that when the axiom of choice fails, and you look at those extreme counterexamples (e.g. amorphous sets), then these look even weirder because choice is in fact very ingrained into our intuition.
To sum up?
The axiom of choice is really not at fault here. It lets us prove the existence of sets which lie outside of our intuition, because our intuition is honed to understand a given structure (e.g. topological structures, group structures, etc.), and it doesn't help when the infinitude of the sets lets us stretch and bend them in all kinds of ways to create weird stuff like the Banach–Tarski Banach–Tarski paradox.
Epilogue?
So there are two more minor points that I want to touch on.
Our intuition is crap. We used to think that functions are "more or less continuous", then we learned that in fact almost none of them are continuous. Then we figured that almost all continuous functions are differentiable, but then learned that almost none of them are... and you see where this trend is going.
If you trace things back in history you run into physics or physical things in many cases. And physics is about phenomenon, things we can see and measures, which we automatically assume are continuous and "make sort of sense". But the mathematical world, as we have it in the post-post-modern era has a lot more to offer, and that sort of clashes with the roots, and sometimes with the intuition we carried from the original motivations.
The axiom of choice is not really to blame. If you deny the Banach–Tarski paradox, and require that all sets of reals are Lebesgue measurable instead, then you can partition the real numbers into strictly more non-empty parts than elements. This is just bonkers. And it's not because of the axiom of choice, that is out the window here. It's because infinite sets are weird.
So what comes next? Next comes the fatalistic understanding that you can do nothing to change this. Unless you want to work in constructive mathematics, in which case you will run into a lot of other weird results, like non-empty sets that have no elements.