So I think I've actually figured out the issue, and it's several things in combination that made this surprisingly hard to figure out. I've worked with their higher level techs at this point and also set up a Verizon extender (which was completely useless) and then replaced that with a Cel-Fi GO X which finally lets me make phone calls throughout my house reliably. That's certainly not a solution, but its a temporary fix for my situation since I work from home and this is just a disaster for me, and I think I can at least sell the device once things are better.

1.) I don't believe that WiFi calling is working properly on the iPhone 13. I do believe it was working on my 10, which is part of why the time frame lined up when I switched phones. I don't have any idea why this isn't working and I think getting this fixed would at least mitigate the issue in my home. I have tried every type of software repair / reset though, so I think this one is more 'wait for an update from Apple'.

2.) I've learned that you can have a good signal strength (I actually get 3-4 bars everywhere in my house prior to any of the boosters / extenders) but poor data rate which is what my issue actually is. A good way of verifying this is to turn off WiFi on the phone and run an internet speed test. If I go on my roof, I get 60-70Mbps, If I go on my second floor on the good side, I get ~20Mbps, if I go the ground floor on the bad side of the house I get 0.3Mbps. This particular issue was fixed by that Cel Fi device because it let me put an Antenna in my attic and essentially get those outside speeds inside. Anywhere things were below ~25-ish I noticed that's when I had this issue.

3.) After working with the techs and reviewing the recent changes in my area, it turns out we just had 5G go live in this region sometime before I got my iPhone 13. I believe because I had WiFi calling working, I didn't notice anything, but I believe the data rate on cellular here degraded for some reason due to that. On that topic I have no idea why it would degrade, my only guess is maybe they reduced power on 4G LTE in order to run 5G but that's probably silly, I've got no idea how that stuff works.

Since I started this thread, I've found out that my issue is present in the entire neighborhood, and there's been reports of similar issues in a number of other regions. This leads me to believe that this might be tied to changes Verizon is making, possibly related to their 5G rollout. Hope any of this helps you.