The AES is a good example of a cryptographic algorithm that is rather not straightforward to implement in an efficient and safe manner.
AES is defined on a 4x4 byte state, and every operation (even the sbox) is defined over GF(2^8). However, fast implementations resemble very little of that definition, and end up being a large number of xor and (large) table lookups. This is a much faster way to do it, on general-purpose machines, but it often leaves you open to cache-timing attacks.
So to come up with a fast and secure AES implementation you need to transpose the state in a way that resembles processing 8 blocks in parallel, and emulate hardware-level bitwise arithmetic on software. This is a so-called bitsliced implementation. By this point the code is much more complex and tricky than the original specification, and it will only actually be fast for parallel modes of operation such as CTR, leaving CBC hanging. Thankfully processors now implement AES round instructions, which simplifies secure implementations, but makes portable implementations difficult.
Cryptographers have learned from this state of affairs, though. New algorithms being created (like Keccak, aka SHA-3) now try harder to make the straightforward implementation secure and reasonably fast by default.
Public-key algorithms, on the other hand, are always tricky to implement, even if the arithmetic itself is not very complicated. One of the appeals of curve25519 (and other so-called "safe curves") is precisely that it is rather easy (but still not trivial) to implement them in a safe manner.