Problem won't be air in the system, air prevents engine coolant circulation and if trapped at thermostat prevents it from opening at the correct temp.
So air will cause over heating, not under heating.
Always good to flush rad and heater core, but again these wouldn't cause under heating only over heating.
Fan clutch would be a stretch causing this issue but could if it was cold enough outside.
The fan is there to circulate air in engine bay and to pull air thru radiator once radiator gets warmed up.
Fan clutch is engaged and disengaged by radiator heat, when rad is cold clutch is disengaged so fan can spin almost freely, it doesn't pull or push much air, giving engine and engine bay a chance to heat up.
On the front of the fan clutch is a metal spring, as radiator heats up in the center that spring gets warmed up and expands, this movement starts to engage the fan blades to spin closer to engine RPMs, pulling and pushing air, this cools radiator when you are stopped or going slowly, the warmer the rad then more the clutch engages.
Cold engine
Start engine and run it for 30 to 60 seconds, this will set the fan clutch to outside temp
(You can also hear this happening on most cars/trucks, loud fan noise on cold start, then it gets less and less after 20 seconds or so)
shut engine off
pop the hood and spin the fan blade, it should spin easily, it will slow down quickly but should spin if you give it a good push or pull.
If it is tight, won't spin at all after letting go of the blades then that could be a problem.
Fan could be over cooling engine and engine bay, not letting engine warm up.
Fan clutch is suppose to "fail safe" in the engaged fully position if there is a problem, since more air circulation is better than less(over heating).
I had an old Dodge pickup with straight 6, I had to put insulation on the heater hoses to keep heat in the cab in cold weather.