apt-get install grub-efi-amd64-bin, after which the script ran successfully. I don't know why grub wasn't properly installed earlier in the setup procedure, but there you go.
I also made two small improvements to the process. During paranoid setup, I used the AES noise fill from here:
In the check and finalize procedure, there's a note that you now have to manually run the update grub script every time you update the kernel. But I know I'm going to forget to do that, so I googled a bit and found this thread, which suggested adding the script to /etc/kernel/postinst.d/ . So I did that, and we'll see if it comes back to bite me in the ass and render this machine unbootable in a year or so.
openssl enc -aes-256-ctr -pass pass:"$(dd if=/dev/urandom bs=128 count=1 2>/dev/null | base64)" -nosalt < /dev/zero > /dev/sdxy