CPU/RAM decode performance, and engineering time to develop better compression algorithms and tune them. e.g. zstd in the last few years is like 10x faster than gzip, but compresses about as well. Great example of how new ideas can lead to better efficiency, separate from just ways to throw more compute horsepower at the problem. (Although that does help massively for multimedia.)
For lossy compression of audio, lots of research was done on what sounded less bad to humans. That took time. MP3 was the first format that was "good enough", using DCT and quantization like JPEG for images, but also using models of human hearing to figure out which sounds the ear / mind wouldn't tend to notice anyway, and could be dropped without affecting perceptual quality. That "psychoacoustic" optimization only really affects MP3 encoders; I don't think that makes decode any slower. (MP3 being slower than MP2 is due to other factors; I don't know the details.)
For video, throwing around a significant number of pixels every frame (the result of decompression) gets expensive in memory bandwidth and space, even if you have dedicated decode hardware. e.g. 1024x576 at 24bpp (RGB) is 1.69MiB just for one decompressed frame, and a decoder needs to store multiple.
(Assuming square pixels, pixel count increase with the square of width or height, so lower rez saves a lot of work, and space.)
But HW decode is an unlikely assumption; I think most people wouldn't want to pay a lot extra for the capability to play back the occasional video, especially before the CD era when storage finally got big enough and fast enough. And make no mistake, video decode hardware that fits in a small block of an iGPU these days might be pushing the limits of technology in the early 90s, and wouldn't be cheap, especially with enough RAM.)
Modern video compression formats (like h.264 and h.265) are quite expensive in CPU even to decode, since they do things like large DCTs (16x16 for h.264 high profile or 32x32 for h.264), and copying blocks of pixels around as references. Also deblocking filtering even inside the "loop", i.e. to produce the picture that can be a reference for later frames.
(In-loop deblocking was one major feature that set h.264 apart from earlier video codecs like DivX / Xvid (mpeg4 part2). Some decoders, like ffmpeg, have a fast-decode option to skip loop-filtering, producing error accumulation until the next I-frame but can speed up software decode some. The higher the bitrate, the less aggressive filtering the encoder would normally request, so it could still be watchable.)
Dedicated hardware decode would help, if even that was doable at the time transistor densities. But probably not, even if practical it might cost a significant fraction of the whole computer, especially with the amount of fast memory that would be needed for holding reference frames.
Modern video formats work by predicting the pixels of one frame from a nearby similar block in an earlier frame. (If it's very similar, maybe just code a motion vector, otherwise that + a residual to be added). They can ask the decoder to hang on to some number of previous pictures, like maybe 4 or so is a common number, and reference any of them with any macroblock. Taking advantage of redundancy between frames (temporal) is huge for quality per bitrate, instead of coding all the details of each frame from scratch, especially if it's a complex but static background, and especially at lower bitrate where you're prepared to accept some artifacting. But it requires more memory in the decoder. And requires motion-search in the encoder to find good candidates out of a huge number of possibilities. Encoding doesn't have to be real-time for this use-case, but more than a few days to encode a few minutes of video would be problematic.
Since other answers mentioned floppy disks being inadequate even for modern compression standards, I though it might be fun to see if that's true. According to an SO Q&A, a good floppy drive could read at maybe 100k to 250kbit/s, presumably talking about 1.44MB 3.5" high-density floppies that were the last mainstream format. So I aimed at the lower end of that bitrate.
With codecs like h.265, you can get down to very low bitrates and still have usable video, like 720x480p30 at 134kbit/s. It doesn't look great, but ok for some DVD extras for example. With audio, a minute of video fits in 1.5MiB. (And that's 64kbit AAC, not like 12k Opus.)
h.265 at 100kbit/s at 1024x576p 15fps - usable quality but decode would take a single core 100MHz Skylake or 400 MHz Core2
If you assume all the engineering time and effort had been put in to develop modern (2013 to 2022) video codecs decades earlier than happened in practice, it would take more horsepower than CPUs had at the time.
Modern video codecs are usable at surprisingly low bitrates, where older would be massively blocky and maybe have to drop frames. It doesn't look good, but 100 or 200 kbit/s (floppy disk bandwidth) is better quality than old 240p MPEG1 videos at 800 kbit/s.
I extrapolated from timing ffmpeg -threads 1 -i foo.mkv -an -dn -f null - at about 630 fps on my i7-6700k desktop with dual channel DDR4-2666, running Linux with ffmpeg n5.1.2. That decodes the video as fast as possible, but doesn't display it anywhere or do anything with it. (It doesn't even convert to RGB, just leaving the decode result as subsampled YUV 4:2:0. It's plausible that video hardware can do that conversion or use the format directly, in an alternate universe where more dedicated HW support for multimedia stuff existed)
15 / 630 * 3900MHz is about 93MHz. Round that up to 100MHz, and that's ignoring any CPU time to copy the decode result to video RAM, or decode audio, or run a UI.
Intel released Skylake in 2015. It's a 4-wide superscalar out-of-order CPU that can get a lot done in one clock cycle. Especially with AVX2, processing SIMD vectors of 32 bytes per instruction, with 3 execution units that can handle AVX2 integer instructions. Quite a lot of person-hours have gone into hand-written vectorized asm to accelerate ffmpeg's software-decode of popular video formats.
Skylake also has large fast caches, like per-core L2 cache of 256KiB, and mine has an L3 cache of 8MiB. Data paths of 64 bytes between L1d and L2, and 32 bytes on the ring bus between L2 and L3. In the mid 90s, having a 64-bit external bus and access to cache with that width was a big deal (P5 Pentium). Skylake load/store execution units are 256-bit wide. (External DRAM is still only 64-bit wide, but dual channel, and caches often insulate the core from DRAM.)
Single-threaded software decode on my system runs at about 630 to 635 frames per second, with Linux's energy_performance_preference hardware P-state tuning setting set to balance_performance. This makes it only turbo up to 3.9GHz, not the full 4.2GHz the CPU is rated for. (But the fans stay silent.) So lets say you were aiming You might aim for decode at say 15 frames per second, to play back at that frame rate. 15 / 630 * 3900 = 92.8 MHz, assuming linear scaling of decode performance with clock speed. (Which should probably be true if you slowed down the DRAM in step with the core clock, but kept the CPU core and caches the same size so they'd manage the same instructions-per-clock. i.e. totally impractical for the 90s.)
So with the complexity of a Skylake, you'd still need to hit 100MHz to decode that video in real time. With lower complexity, you'd need to bump the clock speed up significantly. Lower rez would help but wouldn't be that much of a factor.
On a 2.4GHz Core2Duo (E6600 Conroe from 2006) with DDR2-533 DRAM, I got 92fps for the same test. (It has SSSE3 and 128-bit load/store data paths, but slower pshufb.) 15/92 * 2400 MHz = 391 MHz. So you might need a 400 MHz Core 2 to decode that video.
Lower resolutions are faster
Decode cost seems to scale linearly with number of pixels, e.g. on my Core2 with 360p (240fps) vs. 480p (117fps) vs. 576p (96 fps) for very low bitrate h.265 on a single core. So lower resolutions are much cheaper, since keeping square pixels, pixel count goes up with height-squared (or width squared).
This makes sense: every macroblock of the output has to be handled by copying from the reference pixels somewhere and then applying the iDCT residual if there is one. (Most blocks are inter-predicted from a previous frame or intra-predicted from earlier blocks in the same frame, but some are pure I blocks that are just inverse DCT). Anyway, each output pixel needs a value, and that has to come from some copying + processing work that scales approximately linearly with number of pixels, especially with 8x8 or larger blocks so SIMD can mostly work to full effect.
And h.264 is about 4x faster to decode than h.265 on Core2; some of that may be better software optimization for CPUs without SSE4 or AVX2 in h.264 decode vs. h.265. That CPU was already obsolete when h.265 was new, but was current when h.264 was new. (And such optimizations plus parallelization were actually needed for good software decode of 720p or 1080p video, especially in the days before GPUs commonly had fixed-function HW decode blocks, including on even older CPUs like AMD K8.)
Encoder settings
ffmpeg -i foo.mp4 -c:v libx265 -preset slower -b:v 100k -c:a libopus -b:a 12k -vf fps=10,scale=-2:576 '/tmp/foo 1024x576p10 x265.mkv'
-preset slower tells it to use a lot of CPU time finding better quality-per-bitrate ways to encode. The -2 for horizontal size specifies that the width should be calculated from the height, keeping the aspect ratio, but rounding to a multiple of 2.
h.265 can use such large DCT blocks, up to 32x32, that higher resolutions can be better even if the bitrate is way too low to make each pixel look like the source. Perhaps surprisingly, 1024x576p25 looked less bad than 640x360p25 in a random video I encoded at 100kbit/sec. Everything is blurred and distorted, but some large scale details are a bit sharper at higher rez. (Each DCT block has fewer bits, but conversely it's smaller so distortion at that scale is less visible when the whole image is larger. DCT transforms the information in the image from spatial domain to frequency domain, like an FFT, so quality at a fixed bitrate can be quite similar over a range of resolutions, dropping as you get too low and everything blurs, or you get to high and overhead costs more of your bits leaving fewer for details. And bits per block gets so low that quantization has to get really aggressive.)
Lowering the frame-rate helps significantly, leaving more bits per pixel per frame at fixed bitrate, even though similarity between consecutive frames is lower.
Dropping the frame-rate down to 10 fps improves quality vs. the original 25 or 30 fps, leaving more bits for each frame.
200kbit/s at 854x480p15 is of course a lot better than 100kbis/s, getting to the point where it's possible to not be constantly distracted by the amount of blurring, blockyness, and other artifacting, i.e. that one can kind of watch the video.
h.264 is quite a lot worse at this bitrate. When they claim that h.265 can use half the bitrate of h.264 for the same quality, I think they're probably talking about really low bitrates, like video-conference use-cases or lower, so quality is nowhere near transparent. At high quality, there's no substitute for bitrate; texture details just don't get preserved by any currently available fancy codecs even at high settings. x265 is somewhat better than x264, but not twice as good. But when codecs are already having to accept compromises and make detailed surfaces look like smooth plastic, the new coding tools in h.265 are more useful I guess.
Encode is barely real-time even at 10fps at 576p on a quad-core Skylake, when I use a very high quality-per-bitrate setting (-preset slower with x265 3.5). On my old Core2Duo E6600, 1080p video encoded at multiple seconds per frame with x265 -preset slow, about 40x slower than my quad-core Skylake.
And it takes a lot of RAM to do a good job encoding, keeping lots of frames around to search. Given the coding tools of a modern codec like h.265, encoders that can use them to get a decoder to produce good pictures are still necessary. With technology at the time in the early to mid 90s, I suspect you'd be running into very serious encoder limits in how much quality they could achieve given RAM size limits, even if you were willing to wait days to get a 3 minute video encoded.
TL:DR
This answer was meant to be just a data point about decode horsepower required to play an h.265 video in real time. That's why I didn't also time h.264 or divx, which are more reasonable in terms of CPU requirements.
The other key point I'm making is that I think even hardware decode with custom ASICs would be impractical for 576p or 480p h.265 in the early 90s, with chips the size and clock speed of contemporary RISC CPUs like MIPS or Alpha. Maybe I'm wrong about that and it wouldn't need a chip running hundreds of MHz, but I think it would still be pricy enough to have small market demand, not something that could just get tucked into existing video cards for minor extra cost.
And that algorithms / formats take time to develop, as we gain experience with what works (i.e. what encoders can use effectively while still encoding fast enough to be usable. Offline encoding is fine for many use-cases, even 10x slower than real time. But hundreds or thousands of times slower than real-time is a problem for turn-around times from edit to release. And again, an encoder has to be capable of looking at lots of frames at once to take advantage of some of the capabilities of modern formats.)
