That's not the problem though. You're not trying to stop an eavesdropper knowing you're communicating with a particular server, but rather which hostname you're talking to them as.
To extend the Bob analogy; you're not trying to hide that you're communicating with Bob, but that you're speaking to each other as members of Fight Club.
It's certainly not impossible, although overcoming issues of scaling or increased handshake round trips is a difficulty.
In order to be sure we're talking to Bob, so that it's OK if Bob knows we want his Fight Club certificate, I think we have to incur an extra round trip while we obtain the proof he's Bob and send back the request for Fight Club.
If we try to skip that step, Mallory simply interposes, we send our message to Mallory, believing she is Bob, and she reads it to determine we want Fight Club, we are undone. So we have to wait until Bob proves his identity, and only then reveal that we wanted Fight Club.
Of course, this approach would require the DNS record is authenticated, so DNSSEC is a must, added to which the DNS resolution must be encrypted, so DNS over HTTPS, DNSCurve, etc.
Two small problems I will mention, one of which I'm sure you already know: First, encrypted DNS and DNSSEC are not yet widely deployed, so this isn't the silver bullet many people expected of Encrypted SNI.
Second, for an endpoint which has many unrelated names and certificates - which is the case where encrypted SNI is gaining us a clear security benefit given our packets must have a plaintext IP destination - now they need to try every possible private key to see if they can open our encrypted SNI. This might be a very considerable burden.
The idea was to have a single common introductory keypair which all tenants publish to their DNS, in order to encrypt the SNI. That way there is no need to try multiple private keys.
The lack of DNSSEC deployment is an issue, although there's nothing to stop such schemes being employed on an opportunistic basis. However, when DNSSEC is available for a domain, the scheme should be enforced to prevent a MITM attack.
You can tell a few people near you that "someone" wants to tell something to Bob and an answer from Bob. They tell people near them and so on, until it reaches Bob. He then answers and tells people near him, they tell those who told them and so on, until the answer is delivered back to you. And since no one can hear what people tell each other, no one can assume that "someone" is you and not someone else talking to you in secrecy, many connections away from you.
Think overlay peer-to-peer networks.
But the minimum viable threat model is ISP appliances that do classification and identification of traffic, both passively and actively, like trying to probe for protocols and hostnames. If you are not targeting them, you are effectively doing nothing, but pretend privacy PR. Which is the case with Cloudflare's DNS.
Sure, scaling is harder, but it's not impossible.
If you decide well that's OK, we can do something simpler - everybody will have an infinite set of aliases like "Zanizabo" or "Fylnatis" but they won't be one-to-one shared secrets, alas Mallory simply hears you say "Zanizabo" and she says "Hey, Zanizabo, call Oxymoron" (Oxymoron is an alias Mallory has chosen for this purpose) and soon discovers that Bob answers so now she knows who you wanted to talk to.
Create a key out of nowhere for 2 parties to boot strap communicate safely. (obviously Diffie-Hellman doesn't solve all problems like knowing who you are actually talking to)
If I'm in a city square and I want to tell Bob something, but I refuse to let anybody know that I want to communicate with Bob, it's hard to see what I can do. Bob has no way to know I'm even trying to contact him, so he can't help.