A question because I am ignorant about low-level software.

Are there any self-decoding complex file formats?

I remember when you had to download hundreds of different codec packs in order to watch movies.

Given the size of a movie or audio file, would it be possible to bundle it with a cross-platform (Java?) decoder?

@Edent Challenge with video isn't complexity its performance. You could bundle anything pretty much with a bytecode language format (java, wasm whatever) the question would be can you make it fast enough. For old formats maybe.
The second problem is that you don't really 'decode' a lot of modern formats, you throw them at the GPU in the right manner and magic happens.