If you compile C with libc statically linked in, it'll make executables as large as Rust's. If you compile Rust for dynamic linking, it'll give you hello world as small as you get from C.
$ cat test.c && musl-gcc -static -O2 test.c && echo && du -h a.out
#include <stdio.h>
int main(void) {
printf("Hello World\n");
}
20K a.out echo $(gcc --version) && cat test.c && gcc -static -O2 test.c && echo && du -h a.out
gcc (Debian 6.3.0-18+deb9u1) 6.3.0 20170516 ...
#include <stdio.h>
int main(void) {
printf("Hello World\n");
}
796K a.outNot in my experience.
Other languages do follow a similar pattern too. Free Pascal has its own runtime library which is linked statically to the executable, does not link against libc unless you want to use c library functions (or libraries that themselves may want to link against c), has a much richer library than libc and yet it can create executables around the same size as C (a simple hello world is a 40KB .exe file in FPC).
So, no, the reason for C having small executables is not that C has any head start (besides, with the exception of GCC and Clang, no other Windows C compiler in Windows relies on a C libraries that comes with Windows, although some - like MSVC and C++ Builder - can use it as a dynamic library which may or may not be installed system-wide).
The hairy part is finding the library on the system, and that's a mess that Rust merely inherited. The build scripts are there to run pkg-config, search system lib dirs, and compile a fallback if necessary (next everyone suggests to just have Cargo automatically figure it out, until they see how deep the rabbit hole goes for snowflake libraries like openssl and llvm).