Is Newton's algorithm really this much better than conjugate gradient descent?
The relative performance of different optimization algorithms depends a lot on the particular function you are minimizing.  We certainly can't tell you whether it is really that good for your particular function without knowing what specific objective function you are looking at, but it certainly seems possible to me.

There are some functions where Newton's method will be vastly better.  For instance, with a quadratic function, where a few iterations of Newton's method will suffice to get a very precise answer; yet gradient descent might take many iterations to get similar precision.  This can be partly explained theoretically by understanding that Newton's method often converges quadratically or faster (though for some bad cases it can converge more slowly), while gradient descent typically converges sub-linearly for convex functions or linearly for strongly convex functions (and for bad cases it can converge much more slowly), so in a theoretical sense Newton's method often requires fewer iterations than gradient descent.

Conversely, there are also some functions where (conjugate) gradient descent will be better, for instance because one iteration of gradient descent is much faster than one iteration of Newton's method.  One example would be training deep neural networks, where gradient descent works very well but Newton's method would be painfully slow due to the very high dimensionality and the time it takes to do a single iteration of Newton's method.

I would caution against drawing a conclusion about the performance of Newton's method on all functions, based on an empirical observation of its performance on one particular function (a sample size of $n=1$).