If $|A| > |B|$, then $|A-B| > |B-A|$?
Can it be proven without the Axiom of Choice? I think so. Here’s what I think. Since $|A|>|B|$, there is an injective function from $B$ to $A$ but no bijective function. Suppose for reductio that there is a bijective function from $B-A$ to $A-B$. Since there is a bijective function from $A\cap B$ to itself, i.e. the identity function, that would mean that there is a bijective function from $B$ to $A$. Contradiction, so there is no bijective function from $B-A$ to $A-B$. What remains is to prove that there is an injective function from $B-A$ to $A-B$. If there were no injective function from $B-A$ to $A-B$, then there isn’t any injective function from $B$ to $A$, since there definitely is an injective function, i.e. the identity function, from $A\cap B$ to itself. Contradiction, so there must be an injective function from $B-A$ to $A-B$. Is this correct?
Not without the axiom of choice, no.
Suppose that $X$ is a Dedekind finite set, that is, it is infinite but incomparable to $\omega$. Now let $A$ be $X\cup\omega$ and $B=\omega\cup(\{A\} \times\omega)$. Note that $B$ is countable and that $A\cap B$ is $\omega$. But since $A$ contains a Dedekind finite set, it is strictly larger than $B$.
But that means that $A-B=X$ and $B-A=\{A\}\times\omega$, and those are incomparable.
Indeed, an easy generalization of this argument shows this is equivalent to full axiom of choice, since it implies cardinal comparability. Indeed, your supposed proof begins by saying "if $A-B$ is not strictly larger, then it injects into $B-A$". That right there is the axiom of choice in all of its power.