These were used, yes. I am pretty sure Windows in most of 90s used BMPs, e.g. for backgrounds and in MS Paint. [1] Also, GIF is no replacement for BMP.
Also, as far as I know even stuff like compilers (if they want to support Unicode fully) have to pull in dependencies like ICU, which because of its symbol DB weighs about 30MB.
That's another problem Win 95-era software didn't have to care about...
ICU is a problem of our own making. Computers worked with other languages all the time before Unicode. You could say the same for pretty much any modern dependency.