This one has me stumped. I'm using Messaging.sendEmail(List<Messaging.Email>). Examining the logs I'm finding:
System.EmailException: SendEmail failed. First exception on row 0; first error: UNKNOWN_EXCEPTION,
LetterheadHeader, LetterheadFooter FROM EnhancedLetterhead WHERE Id = '0Rnr00000001bUt'
sObject type 'EnhancedLetterhead' is not supported. If you are attempting to use a custom object, be sure to append the '__c' after the entity name. Please reference your WSDL or the describe call for the appropriate names.: 
Select LetterheadHeader, LetterheadFooter FROM EnhancedLetterhead WHERE Id = '0Rnr00000001bUt' works in the Console query, so it exists
Enhanced Letterhead appears in the profile, but not the ability to modify permissions on either fields or the object itself. Obviously, I can not use EnhancedLetterhead as part of the Lightning emails, but hopefully this is a simple flathead error that someone will recognize.
Submitted This as a service request. Looks like there's an issue as follows:
The issue is not release related as it occurs in Winter '20 as well as Spring '20. In addition, the issue only occurs when the Guest User initiates the action, and not when Admin user does. However, the issue occurs when the Apex class is either "with sharing" or "without sharing", which should mean the user permissions don't matter significantly. Moving forward with the workaround to include the headers directly instead of using EnhancedLetterhead. Support will contact as remediation by developers moves forward.