Any Toyota Techs on here?

I cannot remember that far back if the HVAC system is vacuum influenced or not, but if it is, I would be looking foe rotted and broken vacuum lines.

Couldn't pay me enough to drive a toyota, but that's a tale of woe for another day.:soapbox:
I don't think this is a vacuum problem. Every vehicle I've had would default to defrost if vacuum is lost (or greatly diminished)...I believe this is a gov't requirement. Besides, vacuum would likely be higher at idle than at cruising speed. All the HVAC in my '98 Grand Cherokee is vacuum operated, I'd imagine other makes were back then as well.
Do you maybe have a partially collapsed heater hose or something that would restrict heater-core flow? Some vehicles have a valve in one of the lines that shuts off flow to the core when the AC is on...maybe it's failing?