I wonder if an AI can make a better codec, and if we would think of it as "magic".

There are some interesting advances in neural video encoders and decoders - I suspect it will look a lot like the neural models in DLSS 5 for compression -> decompression/reconstitution. There have been some lossless text-compression neural models built that seem to surpass even high level compression algorithms so with time those could get there.