Why Tcd and Tpd is different in combinational ckt?
Why do you think they should not be different? Technically in VLSI, both of them have different definitions, hence have to be different:
Wikipedia on Contamination Delay:

In digital circuits, the contamination delay (denoted as tcd) is the minimum amount of time from when an input changes until any output starts to change its value. This change in value does not imply that the value has reached a stable condition.

This delay is like min.delay which is more relevant to hold analysis of timing paths.
Wikipedia on Propagation Delay:

Propagation delay, or gate delay, is the length of time which starts when the input to a logic gate becomes stable and valid to change, to the time that the output of that logic gate is stable and valid to change.
Often on manufacturers' datasheets this refers to the time required
for the output to reach 50% of its final output level when the input
changes to 50% of its final input level.

This delay is like max.delay which is more relevant to setup analysis of timing paths.
Illustration (source) :

Apart from due to PVT variations, a logic gate can have different \$t_{cd} \$ and \$t_{pd}\$ for transitions: \$ 0 \rightarrow 1 \$ and \$ 1 \rightarrow 0\$.
EDITS based on OP's edits/comments:
I guess you are asking why the delays are different in different scenarios you have mentioned.
Statically, delays of a gate depends on its sizing and the no. of stages. Dynamically, it is also a function of slew at input (how fast signal changes from \$0 \rightarrow 1 \$ or \$1 \rightarrow 0 \$ at inputs, ie., rising/falling delays), and the output capacitance it has to drive (more outputs to drive \$ \rightarrow \$ more capacitance, hence more delay).

Circuits slow down when hot and speed up when cold.

This is called PVT variations due to operating conditions. When temperature increases, delays increase. When temperature decreases, delays decrease, up to a point called temperature inversion.