UPDATE! (And good news!)
Desperate, I took the shell of my PC to my local PC repair shop (If the PC needed new GPU's or CPU's, I didn't have any to test with, and I'm not comfortable with handling CPU's anyway, so I figured let the shop do it), anyway, they had it on their bench and they ended up reflashing the BIOS (he talked about re-merging it and updating it) and now it boots fine every time!
So thank you, everyone, for your help with this, it's been brilliant and I've learned a lot.
Hopefully, someone in the future with this problem can skip to the end and try re-flashing the BIOS first to save time!
CG