I think Rust and C/C++ are in the same boat here: both can produce tiny wasm binaries of 100 bytes or less. Here's a post about Emscripten generating a 42 byte binary from C:
https://hacks.mozilla.org/2018/01/shrinking-webassembly-and-...
But yeah, as you and others said, while both Rust and C/C++ can do that, there's a lot more going on in the general case. Once you add a malloc/free implementation, or string operations, or anything else, the size increases.
The fundamental issue is that Rust and C/C++ were not designed for this use case. In principle, a new language could do a lot better. If such a language were GC based, it would avoid shipping a malloc/free (once wasm gets GC, that will be "free" for that language). And if such a language had the same string types and a compatible "standard library" with the Web, so that it would just call directly into existing Web APIs, then it would avoid shipping a lot of other code that Rust and C/C++ currently need.
TypeScript, for example, could become such a language. That would probably be the optimal path for creating tiny wasm binaries.