Yep the fan relay is new, and the yellow & yellow-white signal wires were a little corroded near the connectors to the fan relay. So a few weeks back, I cut the wires back until I couldn't see any corrosion and spliced in new wires w/ connectors.

To close this out, I eventually got to the root of this and found the issue to be my impatience (as well as the original cooling fan.) I hadn't had an overheating episode since I put the new fan in, but I also hadn't seen the fan run when I thought it should. So I threw up my hands and brought it to...