Just for the record, I'm thinking it's a power supply issue, as my computer still takes a few tries to start up completely and it still shuts down. I've never seen the CPU temp get too high before it does, so, if it is overheating, it must be spiking in a second.
Another issue is, when the computer does heat up, the fan on it does NOT speed up. Well, maybe an increase of 100 RPM, but that's pretty weak I'm assuming.
So, it looks like my shutdowns are more random. Sometimes when I have a lot of stuff open, sometimes when I have nothing open.
I've cleaned and dusted everything. The GPU is cooler, which is nice, but there is still an issue.