Set-Authenticode appears to incorrectly sign the specified assembly
I've actually figured this out on my own.
My Code signing pipeline step was followed by a strong-naming step. The strong-naming step was changing the hash of the assembly so it no longer matched the hash specified in the signature.
The solution was to move the strong-naming step to happen before the code signing one. Now I can successfully strong-name the assembly, sign it, then after packaging, I can sign the nuget package and all the signatures are valid in the output.