Basically, the term conjugate variables is a bit ambiguous and depends on context. You also need to distinguish classical setting and the quantum setting (only in the latter can you talk about the uncertainty principle and Fourier transforms). In the classical setting, there is a consistent way to approach all those problems: the variational principle. In this case, it is rather position and momentum that are conjugate.
In thermodynamics, you want to optimise a potential (entropy, free energy, etc.) while in mechanics, you want to optimise the action. The Legendre transform then arrives naturally as a Lagrange multiplier method to get rid of the constraint under which you are doing the optimisation.
For example, if you want to maximise entropy $S$ with fixed internal energy $U$, then Lagrange multipliers gives you an equivalent unconstrained optimisation problem. The new potential is $S-\beta U$ which is related to free energy, and thus $U,\beta$ (inverse temperature) are conjugate.
Similarly, in mechanics, you want to optimise the action:
$$
S = \int L(x,v)dt
$$
with the constraint $v = \dot x$, so as a continuous analogue of Lagrange multipliers (can be made more explicit when discretising time) gives to the unconstrained optimisation problem:
$$
S = \int pdx - Hdt
$$
From this perspective, in mechanics, it is not momentum and velocity that are conjugate, but rather momentum and position. This is more consistent with the usual vocabulary of quantum mechanics. While it is true that the Hamiltonian is the dual of the Lagrangian, with momentum and velocity being conjugate, the real quantity you are optimising is the action.
Btw, being related by a Fourier transform is valid once you've quantised the system. From the variational formulation, it is actually straightforward to do so by the path integral formula. The classic variational approach is then obtained by the saddle point method. This method is similar to statistical mechanics, and gives you as well a classical analogue of the uncertainty principle, although the link is not necessarily a Fourier transform.
Hope this helps.
