I have a 97 F250 and I think I know what it is. The resevouir where your fuel/water seperator installs is also a prewarmer for the fuel. If it only does this on cool days and only after it has thoroughly cooled down I would say this is it. Try and plug it in to electric and see if it start ok the next morning if it does this is it.
My truck started that last year and the mileage is similar. I held off replacing it since its over 200.00 plus labor.