Lots of good advice here, but many might be too extreme. I find such all-or-nothing approach intimidating for people who just started to think about improving their privacy situation.

Let’s see… you are angry about bloatware. It can come from two sources - mobile service carrier and phone manufacturer. How to get rid of it?

1. Buy only “unlocked” phones. Then the carrier will not be able to push anything to your phone. You will also be free to change the carrier as you wish.
2. Buy phones from manufacturers that don’t install too much bloatware. Google Pixel has only Google apps, Motorola also is almost vanilla Google. Fairphone is more exotic, but an interesting option. iPhone is OK too if you want Apple ecosystem, but customization is not a thing there.

Now, we are in a privacy focused community and I saw your later comments about Google being an opposite of privacy. I would argue that vanilla Pixel is much better than bloated and locked Samsung already. I see you get recommendations to replace the OS that your new phone might run, and these are valid, but come with significant downsides. There are other ways to improve your privacy stance by changing the way how you use your phone without changing what phone or what OS you run on it.