Okay, I've found a solution. It's not perfect, but it should reduce the problem to less than a second of corrupted video.
You'll need two instances of VLC: one to transcode the video files into a common format, and another to stream to all of the clients.
Here's a command line example of an x264/A52 stream scaled to 640x480. Note the use of the "canvas" vfilter to help lock in the aspect ratio.
<your input here> --loop --sout-keep --sout-transcode-venc x264 --sout-transcode-vcodec h264 --sout-transcode-vb 2368 --sout-x264-keyint 24 --sout-transcode-vfilter canvas --canvas-width 640 --canvas-height 480 --canvas-aspect 4:3 --canvas-padd --sout-transcode-acodec a52 --sout-transcode-ab 192 --sout-transcode-channels 2 --sout-transcode-samplerate 44100 --sout-standard-access http --sout-http-mime video/mp4 --sout-standard-mux ts --sout-standard-dst 0.0.0.0:1234 --sout '#transcode:standard'
The "--sout-x264-keyint 24" is what will cut down the loss of the few first seconds of video. But you can't use "gather" in the output because it doesn't work. At least not here.
Now here's the second instance that will read the first instance's stream, and redistribute it to the clients.
http://127.0.0.1:1234 --loop --sout-keep --sout-standard-access http --sout-http-mime video/mp4 --sout-standard-mux ts --sout-standard-dst 0.0.0.0:5678 --sout '#gather:standard'
The stream on port 5678 will now play without any interruptions whatsoever, and the break-up at the beginning of each file will last less than a second.
If you use an MPEG2 stream, there will be no interruptions whatsoever.
Some file formats may not stream properly at all. I've had a ton of problems with the files available on archive.org. I've had many MPEG2 and MP4 files not stream at all while others would stream properly.
Also, this technique will NOT work at all with Theora/Vorbis material, either from a stream or from a file. The audio is properly relayed, but not the video. I've tried to transcode an MPEG2/A52 stream to Theora/Vorbis in the second mass propagation instance, but the sound keeps going out of sync or disappear altogether.
At least the MPEG2 stream is working properly, which is what I'll be needing the most for my upcoming cable channel.