Cold atoms and ions exhibit unparalleled performance in frequency metrology epitomized in the atomic clock. More recently, such atomic systems have been used to implement programmable quantum computers and simulators with highest reported operational fidelities across platforms. Their strength in metrology and quantum information processing offers the opportunity to utilize tailored, programmable entanglement generation to approach the `optimal quantum sensor compatible with quantum mechanics. Here we report quantum enhancement in metrology beyond squeezing through low-depth, variational quantum circuits searching for optimal input states and measurement operators in a trapped ion platform. We perform entanglement-enhanced Ramsey interferometry finding optimal parameters for variational quantum circuits using a Bayesian approach to stochastic phase estimation tailored to the sensor platform capabilities and finite dynamic range of the interferometer. We verify the performance by both directly using theory predictions of optimal parameters, and performing online quantum-classical feedback optimization to `self-calibrate the variational parameters. In both cases we find that variational circuits outperform classical and direct spin squeezing strategies under realistic noise and imperfections. With 26 ions we achieve 2.02(8) dB of metrological gain over classical interferometers.