I managed to get my Homebrew installation back into shape today. The first problem I was having is that it complained that macOS Sequoia was unsupported:
you’re getting attestations by default probably because you have developer mode enabled; those kind of rate limiting issues are why it isn’t in GA yet
I must have turned developer mode on years ago and forgot about it! Here's the documentation, which also explains why my brew update command didn't work as expected:
When developer mode is enabled, brew update will update Homebrew to the latest commit on the master branch instead of the latest stable version along with some other behaviour changes
Homebrew added a feature recently that checks cryptographical "attestations" on downloaded packages. This is implemented via the GitHub gh command.
The fix was to run this instead, using the HOMEBREW_NO_VERIFY_ATTESTATIONS environment variable to disable attestation checking entirely: