I'm curious why they recommend against 4096-bit certs; they say they mentioned it, but I must have missed it... Is it just because it will make the size of the certificate bigger?
If you can afford 4096-bit certs, or you need them, then you should use them. However, on my laptop, I can only handle 34 connections/second/core with a 4096-bit cert. Such performance is likely to be unacceptable for many uses.
They specifically mention that the certificate size (and that of intermediates, among other things) impacts the message size and thus the TCP packet sizes used during handshakes. They actually explain all of this quite well, just read the entire article [specifically the "Certificates" section].