1 - I plugged each of them into my MacBook and did a restore and update. This was the only way I could get them to OS 16.4.1.
2 - Then a device-initiated restore by holding the top, waiting for it to turn red, then let go after the beeps.
3 - (This is where the actual solution starts although I can't say exactly which of these next steps did it, maybe a combination) I unplugged all other hub devices which was two OG HomePods and three Apple TVs.
4 - I then did a network settings reset on my iPhone which Apple recommended.
A suggestion for Apple would be to get a couple iPhones and KEEP various test iCloud profiles throughout more than one OS cycle. Update, restore to/from backup, and then upgrade to the next device model, next OS, etc. Restore from backup, etc... you know, like how 99.999% of us have to deal with things every time we get a new iPhone. Then only use THESE cluttered iCloud profiles to test HomeKit, HomePods, etc. This constant factory default nonsense is a bullcrap solution for an ecosystem that "just works". And the clearing out of iPhone network settings... the idea that you need to dump all of those saved settings and will then need to re-enter wifi passwords for every friend and relative is ridiculous.