Danke Dieter und Dirk! :-)
Actually, late yesterday afternoon, I finally discovered what the problem was. I was using "-ZZ -Y EXTERNAL" and I did verify all the Cyrus packages. You probably wouldn't believe how far "down the rabbit hole" I went on some of that stuff. It's very interesting what can be done with Cyrus for example. LOL
My problem was that I didn't RTFM! Well, not *enough* of the manual. I neglected the ldap.conf man page. I didn't realize that variables like TLS_CERT and TLS_KEY cannot be specified in the global ldap.conf. So the user-side certs were never being offered up. Once I created a ~/.ldaprc with the proper variables and valid cert, presto it worked.
The thing that was throwing me off is that, unless you bind with a cert, the DSE does not give the EXTERNAL value of the supportedSASLMechanisms attribute. It seems as though I should be able to do a simple bind (if otherwise allowed, which it is on my DIT) and see all the mechanisms available. Turns out that's not the case.
Also, the local4.debug (from the server) and the "-d -1" (from the command line utilities) are not very helpful. Things like "End of file" or "Is a directory", etc, etc, are not the actual problem but are the only related things reported.
Anyway, with the help of a coworker, I did finally RTFM and figured that out. So I just wanted to thank you guys for your assistance and report back that I'm good with this issue now.