nasteretro All but one of these is a result of the apps you have installed and how you're using them. If you have Google Maps installed, it's completely expected that there will be a bunch of connections to the maps servers.
The OS will perform link verification for the links the apps claims it's authorized to handle as explained in https://grapheneos.org/usage#app-link-verification and https://grapheneos.org/usage#other-connections. If you're blocking the requests, it will try again.
izatcloud connection would be the OS retrieving PSDS data via xtra-daemon. The query would be for qualcomm.psds.grapheneos.org on current GrapheneOS unless you switched to using the Qualcomm server instead. izatcloud.net is an older name which was replaced by xtracloud.net to differentiate between PSDS (XTRA) downloads and izat (izat has never been used by AOSP, the stock Pixel/Nexus OS or GrapheneOS).
Location services are off for every app. I uninstalled any app that would be using GPS.
Location permission controls whether apps can obtain location data, not what they can access via the network. Location permission being disabled doesn't mean apps can't connect to those domains. You're using apps or web sites within a browser app which are causing connections to these domains.
PiHole query log
Bear in mind that making network connections doesn't require making a DNS query via the system resolver. An app can connect to a hard-wired IP address. That hard-wired IP address could simply be their own DNS-over-TLS resolver for obtaining IPs for the services they use. DNS queries can also be made without using the result to make a connection, which is common for retrieving data via a TXT record. DNS query results are cached locally based on their TTL so you won't see a query there each time a request is made through the local resolver. You aren't going to be able to accurately monitor connections this way and you aren't able to determine which apps are doing it with this approach. It could all be coming from a single web site you visited in a browser.
I'm thinking of wiping my phone and reinstalling the OS from scratch.
There's really no reason to do this. You can remove the apps, disable the Network permission for them and/or disable app link verification connections if you don't want the OS doing that for your installed apps.
Phone is Pixel3a on the last update.
Pixel 3a has been end-of-life since after May 2022 and isn't secure anymore regardless of your OS choice. You're missing many months of privacy/security patches and many AOSP and GrapheneOS improvements. You're still on GrapheneOS based on Android 12.1 which is a lot different than it is today.
The information at https://grapheneos.org/faq#default-connections is accurate for current GrapheneOS. There are differences for the old release that you're using.
GrapheneOS has used our own PSDS server by default on Qualcomm SoC devices since the 2023050500 release:
Another change was replacing the rest of the DNS test queries with a randomized subdomain of our own domain in the 2023052800 release, but this is an example of a DNS query that's made without using the result to make a connection to the returned IP since it only tests that DNS is working:
There were also changes to Vanadium's connections and perhaps other changes. The current documentation is for the current stable OS release and we don't write documentation on the historical changes.