The behavior of dnf sure looks like you have some weird
options set in the dnf.conf or repo files (like excludes and such).
<facepalm>Boot to the head</facepalm>
Turns out the two systems that failed were the two that get used a lot. On those, I had been having some kind of problem printing that required downgrading the cups packages in order to get it working again, so I had "exclude=cups*" in the dnf.conf file. Remove that and all is well. I was afraid that this was a problem that was much larger than it actually was, and in fact the example I chose is the only place it actually caused an issue.
One of those things where, after tearing my hair out for a few days, someone says "did you check this dumbass thing over here" and that turns out to be it. I don't know why I didn't think of checking the dnf.conf file to begin with.
Thanks to everyone who helped with this issue.
Note to self: <facepalm>remove excludes from dnf.conf before doing a system-upgrade</facepalm>