Tarski proved that, for any set $A$, the set $W(A)$ of well-orderable subsets of $A$ has strictly larger cardinality than $A$.  This is trivial with AC, as then $W(A)$ is the whole power set of $A$ and thus Cantor's theorem applies.  But Tarski gave a proof that avoids AC.

I don't have my copy of Howard and Rubin's "Consequences of the Axiom of Choice" handy, but if I did then I could probably find lots of examples by looking at the various forms numbered 0A, 0B, etc.  I believe all of these are provable without AC (hence the number 0) but there was once a reason to suspect AC was needed.