My gf's horse hauling rig, 01 F250 7.3, had the exact same symptoms. I determined with the meter the relay was bad. I replaced with the hd stancor one. Starts perfectly now in any temp and tested as high as 6000 ft. And I was getting ready to do all new plugs and wire harnesses. Really glad I simply checked the relay before going big with time, money and effort.
If you haven't found the YouTube series from Powerstroke Help, you need to watch his videos. That guy is awesome. I learned a ton. Find the video that talks about changing the oil in the top of the motor. That was another noticeable improvement after I pulled that sludge out and put fresh oil in.