Which phase is more efficient for temperature changes?
A liquid is better than a solid for cooling an object, because it can make more complete contact with the object being cooled, plus it can undergo convection, so the layer of liquid next to the object being cooled is replaced by cooler liquid as the liquid circulates around the object. 

A liquid is denser than a gas (giving better contact with the object being cooled) and also will likely have a higher heat capacity, which translates into a higher "cooling" capacity as well. But don't forget about "wind chill factor" - a moving blast of air is a lot more efficient at cooling an object than stationary air. Convection ovens take advantage of this principle too, but for heating rather than cooling. Liquids will probably be more effective than gases for most cooling applications, but there will probably be some exceptions.