@Joseph Thanks, that one might just work! I'll just have to search the "best" one between the two.

Well I couldn't find the paper, but I've found the Kasa method. It's a simple algebraic method for fitting circles(!). I've read that iterative methods are more robust and accurate, which I prefer over computational complexity here. And since the least-squares method wasn't sufficient, I hardly believe that a simple algebraic method would suffice.

The best geometric fit would be the one with minimal average distances. I've tried the direct approach described in the first paper (first link in my question), and the least-squares approach as described in the second link. I've run the MATLAB code with my data for Newton, Newton-Gauss, and Variable Projection methods. I could've drawn myself an ellipse which better fits my data :) Thanks for the reference, I'll check that soon.