It begs the question: what's wrong with RSA??? I've always heard it's because implementation is hard and ECC magically solves most of these problems, but clearly that's not the case...
The reason not to use RSA is that you're not going to get it right, because it's hard to get right. In cryptography, that makes it intrinsically bad on the merits.
However, for DJB's point there is a major advantage for X25519/X448 specifically: it's hard to get a huge speedup by implementing them insecurely, and the same is not true of RSA.
This is due to the multiplication group modulo a prime (or a pair of primes in RSA) being vulnerable to "index calculus", a faster-than-brute-force way of attacking things.
As the paper says, the main point of ECC is being impervious to index calculus by design, based on an argument by Victor Miller in 1986 about the structure of "point heights" on elliptic curves.
RSA implementations have also led to vulnerabilities in the past, and one of the big claims of djb (as the paper's first author is called in the crypto scene) is that Curve25519 and friends are designed specifically to select, among many secure choices, one that is particularly easy to implement without falling into any of the usual traps.
For equivalent security with ECC (or with AES) at their typical parameters (i.e. 256 to 512 bit elliptic curves or 128-bit to 256-bit AES keys), RSA must use very long keys, even longer than any RSA keys that are used in practice (which are normally no longer than 4096 bits), which makes the RSA operations slow and adds a large overhead to the communication protocols that must send and receive such long keys.
But probably no longer than 2048 bits:
The NSA might have a computer from a crashed alien spacecraft as well but we have to work with what we know. Of course that alien computer is well known to be helpless against RSA and effective against everything else... :)
publicly. The algorithm side and the hardware side are really really different because we can be pretty sure that the NSA doesn't have a giant super computer that is either dramatically more efficient than commercially available computers, or that uses more than say 1% of US electricity consumption. On the algorithm side, we know that the NSA employs a decent number of number theory people, and given the way that math research progresses, it's pretty easy to imagine that one of those people has found a slight algorithmic improvement over public state of the art. CFRAC was invented in the 1970s. QS invented in the 1980s. The NFS was the 1990s with some improvements in the 2000s. If we go another 50 years or so with no progress, it maybe starts to be reasonable to believe that there isn't a secret algorithm that's better, but with 5 improvements in the last 50 years, it seems pretty likely that there could be 1 more that has been found but not published.
It has been partially broken so many times that it's expected it will be partially broken again; (That's how foot-guns are born.)
It is slow and expensive, even more because every time it's broken people have to increase their key size, making it slower and more expensive;
It's very flexible, so that people keep using it wrong again and again. Arguably that could be a benefit, but it's hard enough to make people use it right, making them get an innovative usage right is almost impossible.
Shor’s algorithm is polynomial, however the number of qubits required is in order of O(log(n)^2), where n is the length of the key. Because ECC keys are much shorter (e.g., 256 to 521 bits) than RSA (2048 to 4096 bits), a smaller quantum computer would be needed to attack ECC.
I've only ever seen the claims of 1:1 key bit to qubits. Aren't there existing claimed quantum computers with 20 qubits? Isn't Canada's machine an order of magnitude more qubits?
I think, but I may be misremembering, that you could apply Shor's algorithm to speed up index calculus by going for the subproblem directly? In this case RSA would fall too.
I note that the NSA recommendations are "move to post-quantum crypto", not "go back to RSA" so I infer that they think RSA-4096 might still be vulnerable.
Edit: yes, I read it and it is.