Indeed. I have this problem with my S4 right now - I can't install anything anymore, because something (apparently the OS; INB4 yes, I've checked the obvious things like data caches) grew to take most of it, and I'm stuck at ~500MB free. Most apps can't even be moved to SD card, and those that can be only get moved partially.

In general, it's insane that 16gb is not considered the bare minimum for Android today considering the terrible experience you get with 8.