I just did a fresh install of MacOS Sequoia 15.0.1, then I installed Xcode 16.
Then, in Terminal, I did: xcode-select --install
Which created a pop-up window from which I installed the Command Line tools.
Later that day I used the command "brew doctor", and got this warning:
Warning: Your Command Line Tools are too outdated. Update them from Software Update in System Settings.
If that doesn't show you any updates, run: sudo rm -rf /Library/Developer/CommandLineTools sudo xcode-select --install
Alternatively, manually download them from: https://developer.apple.com/download/all/. You should download the Command Line Tools for Xcode 16.0.
And yes, System Settings -> Software Update showed that Command Line Tools needed to updated.
I find this to be very strange behavior of MacOS Sequoia 15.0.1...