Powering Arduino AND Relays
Linear regulators such as the 7805 operate by dissipating the additional voltage until their rated voltage remains.
This - as you noticed - requires a higher voltage  than the rated voltage.
Some variants, labeled as LDO for low drop-out, have reduced requirements for this, but normal 7805 usually require around 7 V to operate correctly.

The difference to the rated voltage is dissipated as heat as per P = U * I, with U being the voltage difference, and I the current pulled by your circuit.

You can use the switching power supply directly, or use a more advanced voltage regulator like the R-78E5.0 directly from 9 V, which has far lower losses.

Another option would be using the 5V from the switching transformer to drive the (less delicate) relays, and use the 7805 only for the MCU and display, but you would still want to use a heat sink in that case.