We are designing a system that is known to be read-heavy (on the order of tens of thousands of reads per minute). 


There is a table names that serves as a sort of central registry. Each row has a text field representation and a unique key that is an MD5 hash of that representation.1 This table currently has tens of millions of records and is expected to grow into the billions over the lifetime of the application.
There are dozens of other tables (of highly varying schemas and record counts) that make reference to the names table. Any given record in one of these tables is guaranteed to have a name_key, which is functionally a foreign key to the names table. 


1: Incidentally, as you might expect, records in this table are immutable once written. 

For any given table other than the names table, the most common query will follow this pattern:

SELECT list, of, fields 
FROM table 
WHERE name_key IN (md5a, md5b, md5c...);


I would like to optimize for read performance. I suspect that my first stop should be to minimize the size of the indices (though I wouldn't mind being proven wrong there). 

The Question:
What is/are the optimal data types for the key and name_key columns?
Is there a reason to use hex(32) over bit(128)? BTREE or GIN?

The data type uuid is perfectly suited for the task. It only occupies 16 bytes as opposed to 37 bytes in RAM for the varchar or text representation. (Or 33 bytes on disk, but the odd number would require padding in many cases to make it 40 bytes effectively.) And the uuid type has some more advantages.
Example:
SELECT md5('Store hash for long string, maybe for index?')::uuid AS md5_hash;

See:

Convert hex in text representation to decimal number
Would index lookup be noticeably faster with char vs varchar when all values are 36 chars

You might consider other (a bit cheaper) hashing functions if you don't need the cryptographic component of md5, but I would go with md5 for your use case. md5 is well established, very fast and your values are mostly read-only anyway.
A word of warning: For your case (immutable once written) a functionally dependent (pseudo-natural) PK is fine. But the same would be a pain where updates on text are possible. Think of correcting a typo: the PK and all depending indexes, FK columns in "dozens of other tables" and other references would have to change as well. Table and index bloat, locking issues, slow updates, lost references, ...
If text can change in normal operation, a surrogate PK would be a better choice. I suggest a bigserial column with a range of -9223372036854775808 to +9223372036854775807. That's nine quintillion two hundred twenty-three quadrillion three hundred seventy-two trillion thirty-six something billion) distinct values for "billions of rows". Might be a good idea in any case: 8 instead of 16 bytes for dozens of FK columns and indexes!). Or a random UUID for much bigger cardinalities or distributed systems. You can always store said md5 (as uuid) additionally to find rows in the main table from the original text quickly.
Related:

Default value for UUID column in Postgres

For your query, see:

Optimizing a Postgres query with a large IN

What about hyphens?
If you prefer a representation without hyphens, remove the hyphens for display:
SELECT replace('90b7525e-84f6-4850-c2ef-b407fae3f271', '-', '')

But I wouldn't bother. The default representation is just fine. And the problem's really not the representation here.
If other parties should have a different approach and throw strings without hyphens into the mix, that's no problem, either. Postgres accepts several reasonable text representations as input for a uuid. The manual:

PostgreSQL also accepts the following alternative forms for input: use
of upper-case digits, the standard format surrounded by braces,
omitting some or all hyphens, adding a hyphen after any group of four
digits. Examples are:
A0EEBC99-9C0B-4EF8-BB6D-6BB9BD380A11
{a0eebc99-9c0b-4ef8-bb6d-6bb9bd380a11}
a0eebc999c0b4ef8bb6d6bb9bd380a11
a0ee-bc99-9c0b-4ef8-bb6d-6bb9-bd38-0a11
{a0eebc99-9c0b4ef8-bb6d6bb9-bd380a11}


Why not bytea?
The md5() function returns text. You would use decode() to convert to bytea and the default representation of that is:
SELECT decode(md5('Store hash for long string, maybe for index?'), 'hex')

\220\267R^\204\366HP\302\357\264\007\372\343\362q

You would have to encode() again to get the original text representation:
SELECT encode(my_md5_as_bytea, 'hex');

To top it off, values stored as bytea would occupy 20 bytes in RAM (and 17 bytes on disk, 24 with padding) due to the internal varlena overhead, which is particularly unfavorable for size and performance of simple indexes.
What about "invalid" UUIDs?
There are no "invalid" UUIDs.
Octet 13 and 17 encode a "version" and "variant" for certain UUID types. But Postgres' uuid data type accepts all 128-bit quantities without regard to "version" or "variant". That's according to RFC 4122:

Validation mechanism:
Apart from determining whether the timestamp portion of the UUID
is in the future and therefore not yet assignable, there is no
mechanism for determining whether a UUID is 'valid'.

"Version" and "variant" are meaningless / not applicable for this use case. To verify I ran a quick test:
db<>fiddle here
Everything works in favor of a uuid here.
