One file wants to belong to two users. How? Hard linking fails

You can use ACLs so the file can be read by people in both groups.

chgrp bar file
chmod 640 file
setfacl -m g:baz:r-- file

Now both bar and baz groups can read the file.

For example, here's a file owned by bin:bin with mode 640.

$ ls -l foo
-rw-r-----+ 1 bin bin 5 Aug 17 12:19 foo

The + means there's an ACL set, so let's take a look at it.

$ getfacl foo
# file: foo
# owner: bin
# group: bin
user::rw-
group::r--
group:sweh:r--
mask::r--
other::---

We can see the line group:sweh:r-- : that means people in the group sweh can read it.

Hey, that's me!

$ id
uid=500(sweh) gid=500(sweh) groups=500(sweh)

And yes, I can read the file.

$ cat foo
data

You may want to reconsider these statements:

Potential solution: Create a new group barbaz whose members are bar and baz. Let foo belong to root:barbaz.

That looks like a pretty heavy-handed solution to me. Is there no neater, simpler way to share the configuration file foo between the two programs?

Why is it heavy-handed to create a new group? Doing so has the following advantages over ACLs:

• Although you have phrased this as a hypothetical with commands /usr/bin/bar and /usr/bin/baz, it's relevant that these two programs can share a configuration file. This suggests that the programs are naturally related. Creating a new group for them would seem to describe a relationship that actually exists and should trigger behavior (such as permissions to read the common configuration file).
• Solving this problem via groups is portable to every Unix, meaning that you can rely on the same mechanism, working exactly the same way, on any Unix or Unix-like system. ACLs are far more complex and portability can be a problem.

Personally I see ACLs as the heavy-handed solution here, and groups as the simpler, traditional Unix way.

I would think this would be a typical use for Access Control Lists (ACLs). Add both users (or groups) to the config-file's ACL:

/etc/foo  root:root rw-------  # Traditional Unix ownership and permission for foo

$ setfacl -m user:bar:rw- /etc/foo  # Allows user bar to read and write foo
$ setfacl -m user:baz:rw- /etc/foo  # Allows also user baz to read and write foo

You may have to install the acl-package first.