The entropy stems from the words, not characters. With random words and no repetition, you have C(n, k) combinations P(n, k) permutations (or n^k with repetition), where n is your dictionary size and k is the number of words you chain together. These passwords tend to be longer, but not by much. A big enough dictionary can yield some pretty high entropy with only a few words.

I've had passwords as limiting as 16 characters for some services (unfortunately)...

16 characters is hardly enough for random characters unless you include Unicode (which rarely works for those same services that usually have shitty implementations).

Not much can be done there, sadly. You're lucky if they even hash their passwords anyway - you'll probably just get your password emailed to you if you click "forgot password" like it's 2003.

I would never, ever want my users relying on their brain...

I never would either. People should just use a password manager. I was just mentioning an alternative that generated more memorable passphrases, but I wouldn't advocate for it over random high-entropy strings saved in a password manager.