Why does indicated airspeed change with altitude?
As you state, IAS is simply based upon the difference between total pressure and static pressure. For low subsonic conditions:

$$ p_t = p_s + p_q = p_s + \frac {1}{2} \cdot \rho \cdot V^2$$

$\rho$ is the air density, which is a function of air temperature: $\rho = \frac {p_s}{R \cdot T}$. For indicated airspeed, the density at sea level $\rho_{SL}$ at 15 degC is taken:

$$ V_i = \sqrt {\frac{2 \cdot (p_t - p_s)}{\rho_{SL}}}$$

However, the actual dynamic pressure measured by the pitot tube is caused by actual density.


When temperature decreases, density increases.
So at colder temperatures, some of the dynamic pressure is due to higher $\rho$
Therefore, the $V_{ind}$ bit decreases. The pitot only measures dynamic pressure and does not know what is due to temperature 


Air is colder at higher altitude if we stay in the troposphere - climb to over 33,000 ft and the IAS does not change anymore.