Why do fusion and fission both release energy?

In general, both fusion and fission may either require or release energy.

Purely classical model

Nucleons are bound together with the strong (and some weak) nuclear force. The nuclear binding is very short range; this means that we can think of nucleons as "sticking" together due to this force. Additionally the protons repel due to their electric charge.

As geometry means that a nucleon has only a limited number of other nucleons it can "stick" to, the attractive force per nucleon is more or less fixed.

The repulsive electric field is long range. That means that as the nucleus grows, the repulsion grows, so that eventually that repulsion exceeds the attractive effect and one cannot grow the nucleus further. Hence a limited number of possible elements.

Effectively this means the attractive force per nucleon increases rapidly for a small number of nucleons, then tops out and starts to fall.

Equivalently, the binding energy per nucleon behaves similarly.

As @cuckoo noted, iron and nickel have the most tightly bound nuclei; iron-56 having lowest mass per nucleon and nickel-62 having most binding energy.

This image (from Wikipedia) illustrates the curve in the typically presented manner:

However, I prefer to think of binding energy as negative and therefore better visualize iron as being the lowest energy state:

For lighter elements:

• Fission requires energy
• Fusion releases energy

For heavier elements, the opposite is true.

The reason we mainly observe the release energy cases is because:

• It is easier to do
• It is more "useful"

Fission releases energy, because a heavy nucleus (like Uranium-235) is like a cocked mouse trap: it took energy to squeeze all those protons and neutrons hard enough together to make them barely stick (by the nuclear force) against the natural tendency for all those protons to fly violently apart because of their electrostatic repulsion. When struck by an incoming neutron, it is like a mouse touching the trigger pedal of the trap: BANG goes the nucleus.

In the case of fusion, the mechanism is different: the nuclear force between protons and between neutrons is very powerfully attractive but only kicks in when the particles are so close to each other that they are "touching". That attraction is not quite enough to stick two protons together against their electrostatic repulsion but if you add two neutrons to the recipe, you get enough mutually attractive nuclear force to overcome electrostatics and the particles then violently suck themselves together with a very powerful BANG.

Other fusion reactions in which the (2 protons plus two neutrons) get pressed onto a heavier nucleus (like carbon, nitrogen, oxygen, fluorine, ...) release progressively less energy, because it takes more and more work input to overcome the repulsion effect as the nucleus accumulates more protons. By the time you get to iron, further fusion reactions actually consume energy instead of releasing it, because the electrostatic repulsion effect gets bigger and bigger- and you are in the province of fission instead.

Your assumption about the lowest energy state when everything is tightly stuck together is incorrect.

It only goes this way until you get iron nuclei - and this is why iron is the heaviest element created by fusion.

Creating nuclei heavier than iron consumes energy rather than releasing it. And this is why these elements are only created in supernova explosions and other highly energetic events where there is abundant energy input.