The idea I'm thinking of is some kind of fliphone combined with a separate device for everything else. I haven't looked too much into it so I can't guarantee it's a good idea, and after like 2 minutes of searching I couldn't find a flipphone that supported hotspotting.

I just got GrapheneOS, and while it's good I really hate the jumpscare that is the Google logo every time I reboot (since it's exclusive to Google Pixels).

My first instinct is to recommend a recent Pixel with GrapheneOS:

• Make sure to buy a factory-unlocked model so that it's not locked down to the stock OS. Preferably also gently-used second-hand so no money goes directly to Google.
• Of the options, GrapheneOS gives you the most compatibility, security, and updates.
• Installing GrapheneOS can be intimidating at first, but it's pretty hard to mess up if you install through a Chromium-based browser.

I've also used CalyxOS and it's a solid option that supports a few models outside of Pixels. But if you end up needing Google Play Services, you'll be stuck with its replacement microG, while GrapheneOS offers sandboxed full-fat Google Play Services. While still secure, it's not the hardline security of GrapheneOS.

I have no experience with FairPhone or Linux phones. Fairphones' main attractions are the easily replaceable battery and microSD slot. Linux phones are still too cumbersome for the regular user to daily drive.

EDIT: see also this table comparing privacy-focused options https://threecats.com.au/comparison-of-custom-alternative-android-os-roms-grapheneos-divestos-calyxos-iodos-eos-lineageos-stock-android-aosp

In the US, AT&T, Verizon, and T-Mobile have an oligopoly over the cellular infrastructure. All of the other carriers (MVNO) just piggyback off the infrastructure of the big three. Traditional voice calls and SMS ("green bubble") texts are unencrypted and logged, no matter the carrier. Carriers can also perform cell tower triangulation and track the IMEI, which is permanently associated with your phone, surviving even an OS reinstall.

One way you may try to avoid handing over identification at activation or payment for cell service is to buy a 1-year prepaid SIM with a prepaid gift card to a trusted friend's or otherwise shared mailbox. Or buy a prepaid SIM at a brick-and-mortar store with cash and top off with refill cards thereafter.

You have to remove the Sim card. Use WiFi.

You can't have privacy if your phone connects to cell towers. Your Mac address can be randomized. Your IMEI can't

To my understanding it's more based on the phone model rather than carrier. I use graphene, which only supports pixels.

Which privacy first smartphones would people recommend for US users

If you want to run GrapheneOS, then you can only use a Google Pixel.

If you want to run Calyx, you can use any phone on the CalyxOS "Devices" list, which includes Pixels, Fairphone, and some Motorola phones too.

I personally recommend Pixels because they tend to get the fastest and longest-lasting OEM-provided security patches (e.g. the Pixel 8 and later get 7 years of updates from when they were released) and Android releases, and they actually have a pretty decent selection of self-repair kits available for if you need to do a repair yourself, or if you want a repair technician to not have to go through a complicated ordering process for spare parts.

how does it work putting it on a network?

Make sure to buy one that's not locked to a carrier, otherwise you'll be unable to install the custom OS in the first place, since the bootloader will be locked. You can still set it up with any carrier you want once it's unlocked. (this essentially means you need to buy the phone directly from the manufacturer. Don't buy through your phone plan, or through a trade-in/upgrade with your carrier)

Your carrier, once you request it, will either mail you a physical SIM card you can put in your phone, or a digital eSIM you can activate immediately. I prefer eSIMs for convenience, but it's entirely up to you. (you can check out this list of pros and cons if you're interested. They're mostly negligible.)

Do they go on the regular networks like at&t, sprint, Verizon etc?

Yes.

Now, if you're going to install a custom OS, definitely make sure you watch a couple videos and read the official guide for the OS you choose on how to install it. You definitely want to make sure you don't screw it up.

For example, if you're installing GrapheneOS, you might want to use a chromium-based browser (chrome, ungoogled chromium, brave, etc) over something like Firefox, because it sometimes has issues installing via the WebUSB installer, while having no issues with chromium based browsers.

These little details are something you'll want to pick up from those resources so you can actually feel confident when you flash the OS to your phone, and make sure you do it correctly. Plus, you get the upside of knowing more about how exactly the OS protects you compared to stock android.

I personally recommend GrapheneOS if you're good with using a Pixel, since it seems to have some of the strongest security guarantees on top of its methodology around privacy. (Google has very strong hardware security measures that other phones don't always have, which GrapheneOS takes full advantage of)

Alternative OSes for phones use the same carriers as everyone else. You can choose to use your phone on wifi only, without a carrier, to avoid using a carrier. You can also choose to use a VPN to make your data inaccessible to the carrier (although they'd be able to tell what cell towers you connect to).

In order to switch over, check the compatibility information for each of the OSes you're looking at. If you don't have a compatible phone, you'll need to get one. Then you follow the install instructions for the chosen OS. GrapheneOS was very easy to install for me -- I switched to it when my old phone broke.

Look at the list of available phones for each OS and verify that they can use the cell towers in the USA. Most will be able to. Calyx can work with Motorola phones that are cheaper than pixels but last I used Calyx which was years ago it didn't function as well as Graphene with their sandboxed Google Play services. Since you're just beginning I imagine you'll still use some proprietary apps and Graphene will make that transition much easier.