encodings is only the *first* unfrozen Python module that we load - once you get past that, then you'll find that we also load os.py and various other things.

cx_freeze is an illustrative example to look at in that regard, as it preconfigures the interpreter to be able to find the cx_freeze generated zip archive that has the program's Python modules in it: https://github.com/anthony-tuininga/cx_Freeze/blob/master/source/bases/Common.c

The technique that cx_freeze doesn't use yet is to combine the statically linked Python binary and the generated zip archive into a single file (similar to what zipapp does), and adjust the sys.path definition inside the binary to refer back to the executable itself (since executable files can have arbitrary content appended, while zip files can have arbitrary content *pre*pended).

We're always going to require that embedding applications provide a working import path of some kind, so this isn't a bug.

It might be worth converting to a documentation enhancement request though, as we don't really make it clear in https://docs.python.org/3/c-api/init.html what the "minimum viable import set" actually looks like.