My guess is people will start "solving" this kind of problem through multi-call binaries a la busybox.
That doesn't seem so bad, the GNU coreutils Debian package has an Installed-Size of 17.9MB. Though there might be hidden drawbacks I don't know about.
That's a definitely acceptable size, thanks for pointing that out. Yeah a bunch of symlinks should solve the issue. If the binary is kept cached in RAM at least, there should be no overhead in starting it. I think it's pretty rare to have environments that are so memory constrained that they can't hold onto 8 MB of RAM.
Note that not all targets are that small though. Musl has indeed 8.3 MiB, but in coreutils-0.0.12-x86_64-unknown-linux-gnu.tar.gz, the size of the coreutils executable is 12.6 MiB. On the bright side, on the same target, a local build with the cargo features to reduce bloat enabled gives only 7.1M. All these numbers are acceptable.