I'm aware of some theorems like the Banach-Tarski's which yield very counter-intuitive results, however, it's proof is far beyond my knowledge, so I'm looking for some result that is easy to prove and gives a counter-intuitive result, using Choice.
Does anyone know any examples?
On
I don't know how counterintuitive you will consider this, but how about existence of nonmeasurable sets?
It might sound to someone quite intuitive that to every bounded subset of the plane we can assign a real number roughly describing its size. However, as can be proven with help of Vitali sets, it isn't possible to define such assignment of size which would satisfy just a few natural properties (like translation invariance).
On
The additive structure of $\Bbb R$ and $\Bbb C$ is isomorphic (both have the same dimension as vector spaces over $\Bbb Q$). In particular the reals can be seen as a vector space over $\Bbb C$. Actually, even as a $2^{\aleph_0}$-dimensional one, by essentially the same argument!
On
My example might be not so familiar, but I wrote an answer for joy. If we assume the choice, we can prove that the field of complex numbers $\Bbb{C}$ and the field of complex $p$-adic numbers $\Bbb{C}_p$ are isomorphic as a field. At first it seems so weird because they have different topological structure and the fields $\Bbb{R}$ and $\Bbb{Q}_p$ behave quite differently.
It is a consequence of the theorem that every algebraically closed field is completely determined by its characteristic and transcendental degree, and its proof requires the choice. (It is essentially same as the Asaf's answer.)
On
Cauchy's functional equation $$f(x+y)=f(x)+f(y)$$ has a nontrivial (i.e., not of the form "$f(x)=cx$" for some constant $c$) solution.
It's easy to show that such a function must be extremely pathological - in particular, its image restricted to any nonempty open interval is dense! - but the proof that such functions exist via choice is easy.
Note that the usual proof involves viewing $\mathbb{R}$ as a $\mathbb{Q}$-vector space, and taking a basis. (Although we can avoid linear algebra and just build such an $f$ via appropriate induction, after well-ordering the reals.)
On
Theorem. For any set $S$ there is a function $f:S^\mathbb N\to S$ such that, for each infinite sequence $(x_1,x_2,x_3,\dots,x_n,\dots)\in S^\mathbb N,$ the equation$$x_n=f(x_{n+1},x_{n+2},x_{n+3},\dots)$$holds for all but finitely many $n.$
Here $S^\mathbb N$ is the set of all infinite sequences of elements of $S,$ i.e., functions $x:\mathbb N\to S.$ The proof (using the Axiom of Choice) is quite simple and nontechnical; see the Wikipedia page Prisoners and hats puzzle or Problem 5348, Amer. Math. Monthly 72 (1965), p. 1136. You can decide for yourself how counterintuitive it is.
P.S. Quoting from the cited Wikipedia page, here is the "prisoners and hats" formulation, for the case of a two-element set $S=\{\text{red, blue}\}$:
In this variant, a countably infinite number of prisoners, each with an unknown and randomly assigned red or blue hat line up single file line. Each prisoner faces away from the beginning of the line, and each prisoner can see all the hats in front of him, and none of the hats behind. Starting from the beginning of the line, each prisoner must correctly identify the color of his hat or he is killed on the spot. As before, the prisoners have a chance to meet beforehand, but unlike before, once in line, no prisoner can hear what the other prisoners say. The question is, is there a way to ensure that only finitely many prisoners are killed?
If one accepts the axiom of choice, and assumes the prisoners each have the (unrealistic) ability to memorize an uncountably infinite amount of information and perform computations with uncountably infinite computational complexity, the answer is yes. In fact, even if we allow an uncountable number of different colors for the hats and an uncountable number of prisoners, the axiom of choice provides a solution that guarantees that only finitely many prisoners must die. The solution for the two color case is as follows, and the solution for the uncountably infinite color case is essentially the same:
The prisoners standing in line form a sequence of 0s and 1s, where 0 is taken to represent blue, and 1 is taken to represent red. Before they are put into the line, the prisoners define the following equivalence relation over all possible sequences that they might be put into: Two sequences are equivalent if they are identical after a finite number of entries. From this equivalence relation, the prisoners get a collection of equivalence classes. Assuming the axiom of choice, there exists a set of representative sequences -- one from each equivalence class. (Almost everywhere is impossible to compute, but the axiom of choice implies that some set of values exists, so we assume that the prisoners have access to an oracle.)
When they are put into their line, each prisoner can see which equivalence class the actual sequence of hats belongs to. (This assumes that each prisoner can perform an uncountably infinite number of comparisons to find a match, with each class comparison requiring a countably infinite number of individual hat-comparisons). They then proceed guessing their hat color as if they were in the representative sequence from the appropriate equivalence class. Because the actual sequence and the representative sequence are in the same equivalence class, their entries are the same after some finite number N of prisoners. All prisoners after these first N prisoners are saved.
There is a subset of the plane that intersects every line exactly twice. This was the first formal application of choice that I encountered during my undergrads.