One trick you could do is only play one video at once. You can use animated sprites to make a sort of gif animation and play that instead (and this should be pretty fast as you can use 12 fps or a short loop just to not break the illusion). So when the user plays a new video, stop/unload the others and replace them with fake animated textures. You can also do this for the background the whole time, just have it be a texture animation. I believe that should perform well.
