Another classic example is the Schröder-Cantor-Bernstein theorem.

**Theorem.** If a set $A$ injects into $B$ and $B$ injects into $A$ then there is a bijection. 

If AC holds, then this is nearly trivial, since if $A$ and $B$ are well orderable, then the minimal ordinals would have to be the same, giving a bijection. 

But there is a more constructive proof (one not using AC), stitching together pieces of the injections as illustrated in the following figure. 

[![enter image description here][1]][1]

Historically, the distinction between the proofs is important, and actually the history of the theorem and who proved what when is quite complicated. See the [Wikipedia entry](https://en.wikipedia.org/wiki/Schr%C3%B6der%E2%80%93Bernstein_theorem).

  [1]: https://i.sstatic.net/Er9Or.jpg