In the particular case of primality testing, primality testing is easier than factoring mainly because $p$ is prime if and only if $\mathbb{Z}/p\mathbb{Z}$ forms a field. This has a lot of consequences, including that there are primitive roots, and that Fermat's Little Theorem and some generalizations hold. AKS, as well as Miller-Rabin both use variants of FLTFermat's little theorem or applications thereof. For example, AKS relies on the result that if $n>2$, and $(a,n)=1$, then $n$ is prime if and only if $(X+a)^n \equiv X^n+a$ (mod $n$) in the ring $(\mathbb{Z}/n\mathbb{Z})[X]$. What is going on here then shouldn't be counterintuitive. All primes have $\mathbb{Z}/n\mathbb{Z}$ look very similar. But for composites, the behavior of $\mathbb{Z}/n\mathbb{Z}$ is much harder to understand.
If there is something surprising here, it might be that the problem of factorization of semiprimes, $n=pq$ is about as tough apparently as factorization of generic numbers with a few prime factors, since one might expect that if $n=pq$, then the behavior would still be easier to control. But we actually expect that it is tough enough in this case that we've based some cryptographic systems (e.g. RSA) on this being hard.
