The more I think about it, the more I think you are right about the power supply. I thought it must be a heat issue - i.e. when I start playing a game that causes heat to rise in case and that causes CPU/GPU to get too hot and hiccup (and reboot). But that could also be from the GPU starting to pull more power and the power supply not being able to keep up, correct?
Both are correct.
When your GPU heats up, it tries to cool itself by fans. If fans/heatsink is filled with dust, GPU temps may keep rising, until the point of automatic shut down. Same is with CPU. Hence why clean PC from dust.
Same is with PSU as well. It too has fan in it, which can draw in loads of dust, hindering it's operations. And since your PSU is poor to begin with, it doesn't take much for it to act up.
How hard is it to replace the power supply? Should it be as simple as unscrewing it, taking off a few power connectors, screwing the new one in and attaching the (new) power connectors? I have not built or been inside a PC for many, many years.
Quite easy actually.
Your EVGA W1 is fully-wired PSU, meaning that you can not remove the PSU before you disconnect all power cables. Which are: 24-pin ATX, 4/8-pin EPS, 6/8-pin PCI-E (to your GPU) and SATA/MOLEX cables to your drives and fans.
Most proper PSUs nowadays, are fully-modular. Meaning that you connect only those power cables that you need. Main diff to the fully-wired PSU is, that fully-wired PSU has to fit all it's cables, including unused ones, into your PC. Severly restricting airflow.
Here's further reading about PSU modularity: https://www.cgdirector.com/full-vs-semi-vs-non-modular-power-supply/
So, once you get your new PSU, it also comes with guide, to tell what cables are what. Also, you can't connect power cables wrong, since e.g while 4/8-pin EPS and 6/8-pin PCI-E look similar, they are keyed differently and can't be plugged into the wrong slot.
Further reading of PSU connectors, to get you up to speed: http://www.playtool.com/pages/psuconnectors/connectors.html
Here's a video about changing PSU, starts at 02:04;
The tasks done + PSU fan orientation is well shown/talked about. Other info about PSUs in that video, is either poor advice (e.g using EVGA B5 PSU, which itself, at best, is mediocre quality unit), very bad advice (e.g buying used PSU) or completely wrong (e.g PSUs never catches fire and burns your PC/home down).
So, look this video for the actual tasks needed to be done.
You got the same chip as i have in my main PC, Skylake.
A good CPU, that can idle at ~26C, while on load, mine never goes above 55C. Then again, i haven't neglected my PC, instead, i take good care of it.
Fancy, isn't it?
I ordered some compressed air to try and get rid of some of that internal dust.
When you blow out case fans, use your finger to stop fan blades spinning. Since when you make the fan rotate the wrong way fast, it can kill the fan.
Btw, getting an air compressor, in the long run, is both cheaper and more practical, than just buying canned air. Less waste too.