Compression and expansion of an ideal gas is an adiabatic process, i.e. the entropy $\rm (P\rho^{-\gamma}) = const$, where $\gamma$ is the adiabatic constant.
You can rearrange this using the ideal gas closure relation $\rm P=\rho kT/\mu$ to find $\rm (T\rho^{1-\gamma}) = const.$, which is essentially the statement you gave prior, that compressed gases are hotter (becasue $\gamma>1 $ for realistic gases) if their entropy remains constant.
The air in the atmosphere however does not have constant entropy, and thus its $T(\rho)$-behaviour is different from the adiabatic one. Instead, it follows a force-balance, i.e. the hydrostatic law $\partial P/\partial r = -g(r) \rho(r)$ and $g(r) = -GM/r^2$. The resulting density structure from this is $\rho(r) = \rho_0 \times \exp(-H(\frac{1}{r}-\frac{1}{r_0}))$ with the atmospheric density scale height $H=kT/GM \mu$ and 0-index quantities denote density and radius on the surface.
Now we just have to relate $\rho_0$ to other, known quantities, which we can do when assuming that the entirety of the atmospheric mass $\rm M_{atmo}$ is contained in one scale height of the atmosphere, then we get $\rm M_{atmo} = 4\pi \rho_0 H R_0^2$.
One immediately sees that $\rm \rho_0 \sim 1/H \sim 1/T$. This shows that for a colder atmosphere (smaller H), the density on the ground must be larger, when following the force balance instead of entropy conservation.
Short, less-mathy summary:
Compressed gas naturally heats up. If no exchange of heat with the environment occurs, then after some time we can expand the gas, to cool it back to its exact same initial temperature.
This is called an adiabatic process, kind of a central vocabulary from thermodynamics.
Now if we allow for a process to be diabatic, i.e. we allow for the gas to exchange energy with the environment, then it's temperature cannot be set by the adiabatic condition. Instead, we must look to what else is acting on the gas.
A planet's atmosphere is kept by its gravity, and it is the gravitational energy which sets a different behaviour: In a gravitational field, a cold gas volume must be a compressed compressed one, because it does not have enough pressure to resist gravity. Hot gas can expand far up the gravity well of a planet.
This is a bit simplified, as one can of course also have an adiabatic gas in a gravitational field, but I would only go there in this answer, if there is interest.