As requested I'm upgrading my comments to an answer.
To answer the original question it's necessary to understand how much you know about the function. How many derivatives can you readily compute? For instance, strong convexity matters with first-order methods. For second-order methods a similar characteristic of the third derivative probably applies (e.g., self-concordance).
For first-order methods, if you have strong convexity, then gradient search can do quite a good job. If you don't, then consider the so-called "accelerated first-order methods". Theoretically, these methods require Lipschitz continuity, but in practice, you can estimate and adapt the Lipschitz constant and do fine.
For second-order methods, you really can't beat Newton, unless you exploit specific knowledge of your function. That's a big "unless" though.
Another thing we don't know is the computational complexity of computing the values and derivatives. My intuition here is that gradient descent or Newton will be as good as you can expect, with the choice depending on the cost of computing f′′. Unless the second derivative is wickedly expensive, and in your case it sounds like it's not, then Wolfgang wins.
If the billions of problems are closely related, then a warm start from a nearby solution will probably help, especially if you can start within the region of quadratic convergence for Newton.