The compiler and libraries aren't shipped with most operating systems. They are available as additional dowloads for most operating systems, just like any other language and environment. But the biggest linux distros, OSX, Windows, and ChromeOS don't ship with a compiler in the default install.
I would assert, that this could be done in C, python, rust, and go - no libraries just whatever ships with installing the compiler package. Probably others too but I don't know them well enough to say this about them with the same level of confidence.
I will concede that some of the packages to install those languages may be bigger (in the more bytes sense) than gcc + dev versions of the c libraries.
Literally it just does a few syscalls to read from input and write to output, all those syscalls are available in the stdlib of the languages I mentioned. Everything else is just a few simple loops and some table lookups (there is the ncurses version that does it a bit different, but it includes the raw vt100 codes too - I'm ignoring the ncurses version to be kind to your assertions about dependencies).
For the languages I listed you need the same number of binaries, or fewer. For go - you just need the go binary. For python, the same. For rust you need cargo, rustc and ld (vs C's make, gcc, ld). (note ld here is shorthand for all the tools ld invokes too).
As for cpu cycles, you may be right but that is also unrelated to the minimizing dependencies message - although I don't know that the binaries created by rust or go would actually use more CPU cycles, and likely not enough to matter on any computer made in my lifetime.
As for compile times - I don't think python or go would have a noticable difference (python is compiled to bytecode to run on a vm at startup, its not a true interpreter so what I mean is that the python text -> bytecode part will not result in a noticeable startup delay).
Looking at the project code, I can see several ways to make it have lots of additional dependencies in C or any other language. For instance we could consider the ncurses version in the repo itself, that adds a dependency which must be downloaded (ncurses is installed often by default on linux, but ncurses-dev or whatever is an extra install). But why stop at ncurses, we could make it use glib and getopt and so on.
At best, the dependency thing seems orthogonal to the language.
As for packaging - well I just don't believe it would be worse.
It would be the same set of tools to create the package for each of them - for go and rust you wouldn't even need additional OS dependencies to install the package - really it's just a change of the build command and the binary path to copy into the package, though you would for python - fortunately that is included as part of the default for many OSes that don't include make and C.