I know this might sound somewhat obvious in retrospect, but you could've retained something similar to the original background and reduced the size significantly by generating it at runtime --- the code to create a random-looking background may only be not more than a few dozen bytes, and can be the same for multiple resolutions.
For more examples of this technique, see demoscene productions --- the following video was generated by a binary of less than 4096 bytes:
https://www.youtube.com/watch?v=jB0vBmiTr6o
Source code: https://github.com/in4k/rgba_tbc_elevated_source
Explanation: http://www.iquilezles.org/www/material/function2009/function...