You have to read datasheets carefully.

Not all ATXMega chips come with the AES engine, it turns out. I haven't absolutely confirmed it yet, but one contender is the ATXmega384C3 ATXmega32A4U. Unfortunately, it's a TQFP64 TQFP44 - a slight size boost from the 32U2. It's quite an upgrade from the 32u2, but it's only $3 at Digikey (Q:1). Since it does have the AES engine built in, the prospects are excellent for acceptable performance. Unfortunately, the XMega is still only a full-speed USB device, so it'll never beat ~ 1MB/sec, but with no crypto and an 8 MHz SPI clock the 32u2 is hitting 150 kB/sec. It may not only be possible to increase the SPI clock speed with the XMega, but it has a DMA engine, which may make it possible to get rid of (or at least reduce) the inter-byte gaps.

Of course, I have to figure out whether the current code can be massaged to compile for the XMega, and I want to figure that out first before making a prototype.