cheetahprintsweatpants It is possible that you'll get a better answer than mine (for example, perhaps somebody will talk you through locating and trying an old release of the App Store app). But it's already been four hours since your post, so here is my thinking, for whatever it might be worth.
Though in a mathematical sense it is obviously 100% possible to solve this problem, I believe that in a practical sense it is roughly 0% likely, as follows.
There is a small number of people on the planet (roughly 5) who could look at the crash dump briefly, discern what's wrong, and, probably, describe a quick fix. But most of those people are GrapheneOS maintainers who were part of the decision some years back to stop supporting GrapheneOS on the Pixel 3, in favor of supporting newer devices.
There is a much larger number of people who could dig into the problem for one to three days and figure out some fix. But most of those people are unfamiliar with the GrapheneOS app store, and also unfamiliar with building GrapheneOS, so it would take some actual work.
Actually building a fixed version of the GrapheneOS App Store app for mid-2022 GrapheneOS would be some work, because it would involve recreating a four-year-old build environment.
Meanwhile, "factory unlocked" used Pixel 8a devices are available on eBay from plausible sellers for $250.
Overall I'm guessing that for somebody to diagnose and fix this problem would take at least 8 work hours, and it could easily be more like 24. Might it be possible to hire an Android developer to find and fix this problem for $10-$30/hour? Perhaps, but it doesn't seem all that likely, in which case it would arguably be more straightforward to just buy an 8a. It's true that a refurbished 8a from eBay might suddenly break in a month or two, but it's also true that an eight-year-old Pixel 3 might suddenly break in a month or two.
If the goal is to keep using the Pixel 3 as long as possible, LineageOS might be useful. But if the goal is to have a functional sandboxed Google Play infrastructure on a Pixel 3 in 2026, that may require sustained labor by people who are busy with other things (again, including supporting the newer devices, which are used by many more people, so time spent there is arguably better spent).
I wish I had better news, but the stream of new devices to support makes it hard to support old devices, and the GrapheneOS team has historically chosen to end support for old devices once they can't be kept resistant to known vulnerabilities because Google's firmware support has ended.