Hey there! Thank you for your detailed and thoughtful post as well as for giving GrapheneOS a try. I will try to address each point separately, in an attempt to be as thorough as possible.
SubnetMask Prior to installing the apps, I rooted it (I know some will say bad idea, but I use apps like Titanium Backup, which is where the main problem came in, and Root explorer).
Keep in mind that by using root, you're not really using GrapheneOS at that point in significant ways that matter. GrapheneOS assumes that you've installed it and are using it properly with all of the security intact, which root negates. As a result, it is also not really possible for us to provide support for someone using GrapheneOS with root, as it is not the expect way to use the OS.
SubnetMask My guess as to the reason is due to the fact that Play store is sandboxed and how the sandboxed play store installed the apps is different from how they're normally installed.
The Sandboxed Google Play approach that GrapheneOS uses (which I believe is also optionally available on ProtonAOSP) uses a compatibility layer to make it so Play Services/Store etc. can run in the regular app sandbox without crashing. GrapheneOS does not modify the apps themselves, the compatibility layer merely coerces them into using standard app APIs instead of privileged ones so it can function instead of chain crashing.
You can take a look at this post in which I try to provide a non-technical explanation of how it works (as a non-technical GrapheneOS user myself):
https://discuss.grapheneos.org/d/2501-privacy-sacrifice-when-using-google-play-services/5
SubnetMask could probably install most of my apps using Aurora, but what about the ones I purchased like Titanium Backup and Root Explorer, for example (I believe there are a few others as well)? And what about Google apps that I use (Maps, Sky Map and the big one, Voice)? I could use a separate profile for Maps, Sky Maps, and any other 'google' app I use except Voice - that I need to work all the time as I use a Google Voice number for work related calls, although I'm open to any alternatives if there are any better options. Same goes for maps and sky maps.
As mentioned in the post I linked above, one can simply use Sandboxed Google Play in the owner profile. User profiles do provide some benefits, but whether that's something wants to do depends heavily on their use case. I've provided some thoughts on user profiles and the usecase for them here, if you're interested:
https://discuss.grapheneos.org/d/168-ideas-for-user-profiles/2
SubnetMask Would Titanium Backup work if the apps were installed with Aurora, but then how do I install Titanium Backup without Play store, since it's a purchased app? Or can Aurora install paid apps such as that as well?
For you to install your paid app, you'd need to login with your Google account, which you can do through Aurora Store. That said, I'm foggy on the details of whether it will allow you to install an app you've bought regardless. Furthermore, keep in mind that your paid app might require Play Services in order to do license checks, at which point, using the Play Store starts making more sense.
SubnetMask But the big problem is the app data. Even if I can install 99% of the apps using Aurora, if I can't restore the data, that's a problem. Would Titanium Backup work if the apps were installed with Aurora, but then how do I install Titanium Backup without Play store, since it's a purchased app? Or can Aurora install paid apps such as that as well?
I don't know if ProtonAOSP uses Seedvault, but GrapheneOS does. Do keep in mind that's not considered a reliable solution and the plan is to eventually replace it with a much more robust implementation, but maybe this can work for you at this point?
In conclusion, I know that what I will say now is definitely not ideal given your predicament, but I urge you to try GrapheneOS as it is intended and supported - without root. If ProtonAOSP supports Seedvault, give that a whirl. If not, it might take some effort setting up your phone again, which heavily depends on how many apps you uses, but after using GrapheneOS for years now across 2 different devices, I think you'll find that it will be worth it!
I hope that I was able to help at least a little bit.