Valve can’t distribute the codecs legally, but the community sort of can. VLC for example can get away with it because France doesn’t recognize software patents and in general has pretty good interoperability laws. So the codecs exist in open-source form that you can compile yourself. I think Proton-GE does bundle them, and if not I’m sure someone did or at least have instructions to compile with the codecs. We’ve dealt with wmv files in games well before Proton even existed, well before Valve even supported Linux at all.
For the shaders, it’s a normal and one-time thing. Once they’ve been compiled once they’re cached, and then afterwards it doesn’t need to recompile them and you don’t get stutters. What Valve does there is they collect the compiled shaders and distribute them to everyone so it’s faster. So it’ll be a stuttery mess for a couple minutes and it’ll progressively get smoother and smoother as new shaders will become rarer and rarer until they’ve all been seen once.