OK... So I did check my radiator fill-level and found that it was somewhat low. It only took about 1/4 to 1/2 of a gallon to re-top it however.

The heat inside did seem to be a little better after that, but only by maybe 3 to 5 degrees? It was also still much better up at highway speed than when I slowed down into the 30mpg range... Could it be that at highway speed the sheer speed of the water pump is moving coolant around and through the heater-box radiator for inside, and when moving slower, it's not enough to push past a dead or almost dying auxiliary pump in the heater box tube-flow path? As in... at lower speeds, the auxilliary pump does the work of moving coolant through the heater-box exchange, but at highway speed the coolant/water-pump supplies enough pressure to do it better?

Just throwing out ideas here.. what do you all think?