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 & \text{Sign of}~ΔS & \text{Spontaneity} \\ \hline + & + & \text{The reaction is spontaneous at high temperature} \\ + & - & \text{The reaction is never spontaneous} \\ - & - & \text{The reaction is spontaneous at low temperature} \\ - & + & \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.

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