MacBook Pro connects to iPhone and iPad hotspot, but not data
Solution 1:
It seems you may just be lacking a working DNS configuration.
If iCloud Private Relay is on, your DNS queries from Safari should go through the relay, not go straight to your ISP. IF they go to your ISP via the relay, the ISP's DNS servers are not likely to respond. Why? Typically, it's advised when setting one up to serve a network's own users, to NOT allow a DNS server to act as a public DNS server. So since it's likely your ISP isn't running a public DNS server, it won't respond to queries that appear to come from outside its network. (The few companies that do run public DNS servers generally don't use those same servers to host the DNS records of their own domains.)
However, if retesting confirms that "Turning off iCloud Private Relay on both devices did not fix the issue." then there's another problem as well. (Could be the problem I identified plus bad caching.)
Solution 2:
In my case this was indeed a DNS issue. I hadn't changed any DNS settings (and I even formatted my Mac to make sure things weren't in a bad state)
As a recap, I could ping IP addresses fine including my default DNS server from ISP and 1.1.1.1 and 8.8.8.8 but I couldn't resolve domains.
Turning off iCloud Private Relay on both devices did not fix the issue.
Explicitly setting my DNS to my ISPs DNS server did not fix the issue.
However, explicitly setting 1.1.1.1 as my DNS server (on my MacBook Pro) did fix the issue.
Additionally, after turning iCloud Private Relay back on, it didn't break anything. Which is weird since it explicitly says on the DNS screen that while it's Private Relax is on, you can't manually set DNS settings.
Because of that I'm still not clear on exactly why this happened but hope that helps someone. And I'm curious if anyone has theories on what it was?