I intentionally left that out there in my final version. Originally I had it normalize there, but ultimately decided that the initially-constructed Certificate should be fully representative of any parsed state. Once it's been committed to the database and loaded back out, we'll be dealing with a normalized version, but we use a newly-constructed Certificate partly for verification and then logging purposes, so keeping it as consistent with the source data at that stage is important.

Went ahead and put this in the match_host() change.

So here are my thoughts on normalization.
There are two reasons to normalize:

When comparing hostnames, making sure that two different-cased but otherwise identical hostnames are equal.
When dealing with the filesystem.

These ultimately may have very different normalization approaches as we go forward. We will likely, for instance, need to normalize Unicode characters in a cross-filesystem manner, encoding/decoding characters, but we wouldn't want to represent that version in our objects that way. Similarly, as above, we want to avoid straying too much from the original input too high up.
So I see the hostname handling as follows:

On the high-level classes (Certificate, etc.), we take the raw input as-is, and do not normalize.
In the storage classes (FileStoredCertificate, FileStoredCertificateFingerprints, etc.), we can work with a normalized form for comparison purposes, because we're dealing with a wrapper around certificates and not certificates themselves. We're dealing with comparisons and lookup. So those objects can take that form.
When dealing with the filesystem, we're dealing with a separate normalization, one for storage purposes. This is independent of any normalization that may have been done for comparison purposes. I'm going to make that more clear in the code.

Given that, we don't want to normalize here. Normalization will happen when building FileStoredCertificateFingerprints, and storage normalization will happen in _build*.
I'm also going to be improving storage normalization, so they'll be differing anyway.

So the following is based on using .encode('idna'), and I spent all this time writing this, but things change with the idna package. I'm looking into that now.
We're encoding for IDNA, and it ultimately doesn't matter in this case which we use when using .encode('idna'). lower() is cheaper (casefold() is more aggressive in how it modifies things), but .encode('idna') will do the right thing with either. When Unicode characters are present, it'll ultimately lowercase it all correctly, but when not, it'll leave it alone. So here's how it ends up working:

# Differences between lower() and casefold() for a string with certain mixed-case unicode characters:
>>> 'Straße.de'.lower()
'straße.de'

>>> 'Straße.de'.casefold()
'strasse.de'

>>> 'Éxamplé.COM'.lower()
'éxamplé.com'

>>> 'Éxamplé.COM'.casefold()
'éxamplé.com'


# IDNA encoding with mixed-case Unicode and mixed-case ASCII:
>>> 'Straße.de'.encode('idna')
b'strasse.de'

>>> >>> 'FooBar'.encode('idna')
b'FooBar'

>>> 'Éxamplé.COM'.encode('idna')
b'xn--xampl-9raf.COM'


# Combining the two:
>>> 'Straße.de'.lower().encode('idna')
b'strasse.de'

>>> 'Straße.de'.casefold().encode('idna')
b'strasse.de'

>>> 'Éxamplé.COM'.lower().encode('idna')
b'xn--xampl-9raf.com'

>>> 'Éxamplé.COM'.casefold().encode('idna')
b'xn--xampl-9raf.com'


Okay, that was fun. Now all that said, the idna package has a uts46=True mode, which is probably the right answer if we go with this package. It handles further normalization for user-provided domains.

I can't find anything indicating it's a dependency of cryptography. I only have it through requests. The cryptography source doesn't reference it except as a suggestion in an error message when failing to encode a provided hostname. If we want to use this, we'll need to add it explicitly.

Worth pointing out, this module's a little bit heavyweight compared to the built-in stuff.
I'm trying to decide if this is overkill or not. We ultimately just need something we can store in a predictable format. The IDNA version may not matter too much, but I need to learn the differences between them (and figure out what happens if the encoding changes).