Linux

this distribution allows you to have multiple versions of the same library to work with different programs at the same time, correct?

That is correct. You can even have programs from entirely different releases running on the same system without conflicting with another; one with i.e. glibc 3.34 and one with 3.37 for example. Or even wilder setups with some packages using musl, other glibc and others yet being built statically.

Does this mean that each program downloads all its dependencies independently?

Each program references all of its (exact) dependencies. Nix then looks at the program and its references and builds a tree of dependencies.
Then it tries to "realise" these dependencies (make them, well, real), possibly by substituting (downloading) them from a binary cache or automatically building them on your machine if they're not available in any configured cache.

However, if some package with the same exact version already exists in the Nix store, no action will be taken. Why should it, it's already there.
For example, if you were in an empty world and built an environment with hello and coreutils in it, they'd both depend on glibc. If both came from the same revision of Nixpkgs, chances are that they depend on the exact same version of glibc.
What Nix would do here is fetch 1x glibc, 1x hello and 1x coreutils.

Note however that you don't need to manage any of this. You just say "I want hello and coreutils". Nix takes care of getting the correct dependencies in place but they won't be in your immediate environment. When you then say that your environment should no longer contain hello, it does that. At this point hello will still exist in the Nix store but it won't be in your PATH any longer, so it's not polluting any shared state; it just sits there on disk and the worst it could do is waste disk space. It's not "installed" in the same sense as what it'd mean to have an unused dependencies installed on an FHS system.
In order to reclaim disk space from unused Nix store paths, you can simply run a garbage collection. You don't need to care about that one specific hello store path here though, you just say "remove all unused store paths for me, thanks" and Nix removes it along with all other unnecessary paths. In NixOS, you can even have that ran periodically for you.
(Note that this is distinct from autoremove and the like; those "clean up" the shared state and free up disk space. In NixOS, these are separate processes and dependencies which you don't explicitly declare are never in the shared state to begin with.)

You see, while this could be seen as "bloat", it has none of the negative consequences bloat has on other systems such as more packages for you to manually manage, more binaries in your PATH or weird interactions of other programs. It's just easily managed disk space and disk space is honestly quite cheap.