they ask all the relays they are connected to

This is just dodging the question.

How do I know which relays to connect to? What if none of the relays I connected to are the one that relays notes from the npub that I want to follow?

"Gossip" is just a happytalk phrase... it doesn't scale without a distance metric, and a DHT is nothing more than gossip plus distance metric. You can't expect to connect to everybody on the internet, so as you gossip your way around, you need a way of figuring out if you're getting closer to or farther from your goal. That's what a DHT is.

If you have suggestions to building nostr the way you prefer a distributed protocol to be, you may want to post those here: https://github.com/nostr-protocol/nips

I'm seriously considering it. Posting here was a sanity check to make sure I wasn't missing some obvious existing solution.

Kind of put off that they require a github account though instead of using NIP-34.