Lovelock Gravity at the Crossroads of Palatini and Metric Formulations