How are relays not published anywhere? A very basic property of onion routing is that the client chooses the relays. Even if they are not technically "published", they certainly are public.

Correct! The list of relays (both exit and non-exit) is public. There are several tools with web frontends available as well. There are also relays that are not publically advertised but available by special requests if someone needs a "secret" entry point to the network, they are the so-called bridges,

I've seen this (running a non-exit relay), though in my experience it's been a tiny fraction of sites rather than a majority. I don't get the CAPTCHA prompts for CloudFlare (unless I'm actually browsing via tor, not just my own IP address).

Sites like https://atlas.torproject.org/ will list (exit and non-exit) relays.