What kind of accounts are you trying to log in as? Are they accounts on that Mac or are they Sharing Only accounts. Are they the same as the account you are using on the client?
With Connect to Server, you can use:
smb:
That forces it to try the user you want before trying the current logged in user.
I have a couple of setups, the primary being a Time Machine Sharing Only user. That connects automatically without issue.
The user accounts on both my Macs are the same. When I click on my "host" Mac from my laptop, it connects instantly. It is almost immediate which is a tremendous change over past connections before Sonoma.
How complicated would it be to flush everything and reconfigure it all?