You are used to the fact that the internal energy is minimized in equilibrium, but keep in mind that in this case your system is not isolated. Instead, you are dealing with a system in the canonical ensemble, so there is a giant temperature reservoir coupled to your system! The entire system of your spins + the bath is considered to be in the micro canonical ensemble, and their internal energy is minimized in equilibrium. By introducing the Helmholtz free energy
$$F=U-TS$$
you are able to solve the spin system while discarding the bath. Now observe that there is interplay between the internal energy and the entropy. For low temperatures $F\approx U$ so the internal energy is minimized, while for high temperatures $F\approx-TS$ and the systems tends to maximize its entropy. In between the situation is more complex. Thus as you said $F$ is more fundamental.
EDIT 1: Why minimization? Just because entropy is always increasing! If $Q_{\rm bath}$ is the heat flowing into the heat bath then
$Q_{\rm bath}=\Delta U_{\rm bath}=-\Delta U_{}$
since the total energy of the spins + bath is constant, and so the total change in entropy is
$$0\leq\Delta S=\Delta S_{\rm bath}+\Delta S=\frac{Q_{\rm bath}}{T}+\Delta S=$$
$$=\frac{T\Delta S-\Delta U}{T}=-\frac{\Delta\left(U-TS\right)}{T}=-\frac{\Delta F}{T}$$
Thus the change in Helmholtz free energy is
$$\Delta F\leq 0$$
It means that this quantity is decreasing, obtaining a minimum at equilibrium. I should note that I'd assumed that the system does zero work.