Assuming you are really paranoid, and each is 256 bits of the best CSPRNG output available, then for a table containing 1 million records you are only talking about an additional ~32 megabytes of overhead.
With modern CPUs and most applications, this extra amount of data is not going to move the needle at all.
You can use AES to generate and store the ExternalId column. As you pointed out, this saves you from having to encrypt/decrypt it on the fly every time, at the cost of an extra lookup and some storage (you're going to want an index on that column as well).
If it ever comes up that you prefer to do it on the fly, you can just drop the column. All your external references will still be valid since the ExternalId was generated deterministically.
Possibly only doing one round of aes or skipping the key expansion steps would make it more scalable but I didn't have the knowledge to do that securely.