This doesn't strictly require a PC. There's this trick with using the wireless debugging feature to connect the phone to itself. You can do it with a terminal app like Termux but Shizuku is a nice GUI that streamlines this process and exposes an API for other apps to use. After a quick web search I found https://github.com/samolego/Canta which is, again, a GUI app that uses Shizuku to uninstall apps via adb.

I agree that it's not easy, but anyone sufficiently annoyed by these non-otherwise-removable apps who is able to follow instructions should be able to get it done without needing a computer or special knowledge or messing with the command line.