That's the trick, they actually don't provide precompiled shaders as you know them. The graphics hardware back then was fixed function pipelines with a tremendous number of options to configure how they work. The downside is that you can't run truly arbitrary code but the upside is that they can instantaneously switch behavior as fast as setting a register.

Prior to ubershaders the emulator took a configuration for the hardware pipeline and turned that into a shader, which took time to compile. Ubershaders work by emulating the entire fixed function pipeline in one glorious shader until the smaller, more efficient shader can be compiled and slipped in.

Basically, the ubershader is the only thing that can actually understand the "shaders" packaged with the game and start using them with zero latency.

Why not just precompile all the possible hardware combinations? There's far more combinations than atoms in the universe. Why not just precompile all the hardware combinations that the game actually uses? There's no way to tell before hand without examining every branch of the game's code which ranges in difficulty from "computationally prohibitive" to "fundamental theorems of how computers work says this is impossible".

The article mentions that some users actually passed around cached shader packs, but that solution was brittle.