the real frozendict was the standard library we neglected along the way

If you need a quick immutable representation of dictionaries, but can't be bothered with a 3rd-party library, why not try frozenset(dict_items)?

It is immutable. It is in the standard library. It is unordered, so you're guaranteed that frozenset([('a', 1), ('b', 2)]) == frozenset([('b', 2), ('a', 1)]). And it is the case that, for dictionaries with all immutable values (which is implied by the problem statement anyway), dict(frozenset(d.items())) == d.

Now, yes, it is possible to create a frozenset that isn't a valid representation of a dictionary (e.g. if not all(len(item) == 2 for item in something_which_isnt_dict_items)). But that won't happen by calling frozenset(dict_items). 🙂

And if the above really isn't fancy enough for you, maybe try this on for size:

import collections.abc

class frozenmapping(frozenset, collections.abc.Mapping):
	def __iter__(self):
		yield from (k for k, v in super().__iter__())
	def __getitem__(self, key):
		missing = object()
		value = next((v for k, v in super().__iter__() if k == key), missing)
		if value is missing:
			raise KeyError(key)
		return value
	def __contains__(self, key):
		# skip frozenset and force use of abc.Mapping's mixin
		return super(frozenset, self).__contains__(key)
	def __eq__(self, other):
		# skip frozenset and force use of abc.Mapping's mixin
		return super(frozenset, self).__eq__(other)
	def __neq__(self, other):
		# skip frozenset and force use of abc.Mapping's mixin
		return super(frozenset, self).__neq__(other)
	def __new__(cls, mapping_or_iterable):
		if isinstance(mapping_or_iterable, collections.abc.Mapping):
			items = mapping_or_iterable.items()
		else:
			items = mapping_or_iterable
		return super().__new__(cls, ((k, v) for k, v in items))
	def __repr__(self):
		if not self:
			return f'{self.__class__.__name__}()'
		d = dict(self)
		return f'{self.__class__.__name__}({d!r})'
	# We didn't "have" to implement this; abc.Mapping would "have our back", kinda
	# but we will implement it to avoid O(N^2) performance
	def items(self):
		yield from super().__iter__()

The handy thing about collections.abc.Mapping is that all you need to provide is __getitem__, __iter__, and __len__, and that class will magically "mixin" all the remaining mapping methods (__contains__, keys, items, values, get, __eq__, and __ne__) that you didn't implement to create a fully featured dict-a-like class. (Actually, it's not fully featured since this one's not mutable—obviously, per our goal today—if you want a mutable mapping instead, look into collections.abc.MutableMapping.)

Going over each of the methods:

• __iter__ and __getitem__ are implemented entirely by us.
• We didn't implement __len__, since we're inheriting correct behavior from frozenset.
• items was implemented by us only for run-time efficiency, since the abc.Mapping mixin would, if we hadn't implemented it, iterate through the items, take the key from that item, and then call __getitem__ (which iterates through the sequence again looking for the item it just got the key from) for each key, which is obviously horribly inefficient. Since we know that our underlying datastructure is already just items, we use it.
• __contains__, __eq__, and __ne__ weren't exactly implemented by us. We were just lazy and used abc.Mapping's mixin. But, to do this, we had to skip frozenset's incorrect-for-us behavior in the MRO to "convince" abc.Mapping to kick in with its dict-a-like behavior. This showcases use of super.
• __new__ is basically as described in the first half of this post, plus a codepath to handle dict_items sequences, plus a structured iteration to provide similar protective behavior to dict([('Key1', 'Value1', '\U0001F4A91')]).
• __repr__ is optional but very convenient.