This is a very annoying problem I have also encountered many times.
For some reason it thinks you don't have enough space even when you clearly do.
Sometimes it can refuse a <1mb app when you have about 100mb free. Or it can allow a <100mb app when you have roughly 300mb free.
I don't think there is a real 'fix' to this.
Freeing up even more space should solve the problem.
You can just uninstall a bunch of apps and see if it works again.
Or you can clean your caches and other files you don't need (like the log mentioned by David Balažic) with an app like SDMaid or 1TapCleaner or whatever app you use.
Cleaning cashes/tombstones/logs can easily free up a lot of space for you to install whatever app you like.
The problem will return though once you run out of space again.
the, arguably, best solution would be to have fewer apps installed (I don't like this but it's what works best for me) or buy an sdCard and install apps on sdCard (with the help of an app like AppMgr III or similar).
For those with a Samsung device that splits memory in Sdcard and USBStorage, you'll have to find a different way to actually put the apps on the external sd card instead of USB Storage. I believe I read somewhere it is possible by factory resetting phone and then choosing to install apps on sd or something like that but I am yet to try that.