How can enthalpy change of a system be negative while entropy change is positive? $$\Delta G = \Delta H_\text{system}-T\Delta S_\text{system}$$

$$
\begin{array}{ccc}
\hline
\text{Sign of}~ΔH &amp; \text{Sign of}~ΔS &amp; \text{Spontaneity} \\
\hline
+ &amp; + &amp; \text{The reaction is spontaneous at high temperature} \\
+ &amp; - &amp; \text{The reaction is never spontaneous} \\
- &amp; - &amp; \text{The reaction is spontaneous at low temperature} \\
- &amp; + &amp; \text{The reaction is always spontaneous} \\
\hline
\end{array}
$$

When enthalpy change is negative, the reaction is exothermic, which means it releases energy into the surroundings. If the system is losing energy, shouldn’t the entropy of the system always decrease? I understand mathematically that $\mathrm{d}S = \mathrm{d}Q/T$, and if there is heat exchange, then entropy change can be positive.

But intuitively, if energy is taken away from the system, shouldn’t the entropy of that same system decrease? For some reason, I always thought that more energy means more entropy.
For example, suppose you have a solid block of TNT.

It explodes and releases much energy. $\Delta H$ is negative.

Gaseous products like nitrogen, carbon dioxide and water vapor are formed. The system has become more disordered, so entropy has increased.