That is surprisingly huge. I’ve inspected the .deb package contents, and the /usr/bin/coreutils file is in the package is 23.7Mb. According to the debian/rules file, the build command it runs is make SELINUX_ENABLED=1 PROFILE=release MULTICALL=y, which on my machine creates a 13.1MB file when building uutils from git (on commit 044b33d8cb147d63205f1ef562b5a2ce2bcee7c7) and running strip on the resulting binary. I wonder where the extra 10MB came from?
The debian/rules file messes around with LTO by editing the Cargo.toml file under some conditions; perhaps it disables full LTO in more cases than it should. Switching from lto = true to lto = thin in Cargo.toml when building from git results in a 17MB file.
Not sure where the remaining 6MB came from. Doesn’t seem to be debug info, or at least running strip on the binary from the .deb package doesn’t do anything. I would be surprised if this overhead isn’t avoidable.
There is also an easy win for binary size by using release-fast profile instead of release. That applies panic = "abort" and would cut another 1MB off the binary size. Unfortunately building through make does not support the release-fast profile currently; make just silently falls back to debug profile if you try to tell it to use release-fast. You would need to either get the upstream makefile fixed, or just patch in panic = "abort" into the Cargo.toml as a distribution patch.
If I run cargo build --profile=release-fast --features feat_selinux,unix (which the makefile seems to boil down to) on the git repo of uutils, I get a 12MB binary after stripping. This is half of the current size of the binary in Ubuntu repositories.
It is possible I am missing something, but there are clearly opportunities to reduce binary size still remaining, via panic = abort if anything, although I would be very much surprised if LTO is working as intended when that 23.7MB binary is produced.