Could someone please convince me that there is something natural about
the choice of the Lagrangian formulation...
If I ask a high school physics student, "I am swinging a ball on a string around my head in a circle. The string is cut. Which way does the ball go?", they will probably tell me that the ball goes straight out - along the direction the string was pointing when it was cut. This is not right; the ball actually goes along a tangent to the circle, not a radius. But the beginning student will probably think this is not natural. How do they lose this instinct? Probably not by one super-awesome explanation. Instead, it's by analyzing more problems, seeing the principles applied in new situations, learning to apply those principles themselves, and gradually, over the course of months or years, building what an undergraduate student considers to be common intuition.
So my guess is no, no one can convince you that the Lagrangian formulation is natural. You will be convinced of that as you continue to study more physics, and if you expect to be convinced of it all at once, you are going to be disappointed. It is enough for now that you understand what you've been taught, and it's good that you're thinking about it. But I doubt anyone can quickly change your mind. You'll have to change it for yourself over time.
That being said, I think the most intuitive way to approach action principles is through the principle of least (i.e. stationary) time in optics. Try Feynman's QED, which gives a good reason to believe that the principle of stationary time is quite natural.
You can go further mathematically by learning the path integral formulation of nonrelativistic quantum mechanics and seeing how it leads to high probability for paths of stationary action.
More importantly, just use Lagrangian mechanics as much as possible, and not just finding equations of motion for twenty different systems. Use it to do interesting things. Learn how to see the relationship between symmetries and conservation laws in the Lagrangian approach. Learn about relativity. Learn how to derive electromagnetism from an action principle - first by studying the Lagrangian for a particle in an electromagnetic field, then by studying the electromagnetic field itself as described by a Lagrange density. Try to explain it to someone - their questions will sharpen your understanding. Check out Leonard Susskind's lectures on YouTube (series 1 and 3 especially). They are the most intuitive source I know for this material.
Read some of the many questions here in the Lagrangian or Noether tags. See if you can figure out their answers, then read the answers people have provided to compare.
If you thought that the Lagrangian approach was wrong, then you might want someone to convince you otherwise. But if you just don't feel comfortable with it yet, you'd be robbing yourself of a great pleasure by not taking the time to learn its intricacies.
Finally, your question is very similar to this one, so check out the answers there as well.
I) Not all equations of motion (eom) are variational. A famous example is the self-dual five-form in type IIB superstring theory. In classical point mechanics, frictional forces typically lead to non-variational problems.
II) Consider for instance $n$ variable $q^i$ and $n$ eoms,
$$\tag{1} E_i~\approx~ 0, \qquad i~\in~\{1, \ldots, n\}. $$
A simplified version of OP's problem (v3) is the following:
Does there exist an action
$$\tag{2} S[q] ~=~\int{\rm d}t~L$$
such that the Euler-Lagrange derivatives
$$\tag{3} \frac{\delta S}{\delta q^i}~=~E_i $$
precisely become the given $E_i$-functions?
The above restricted problem is relatively easy to answer once and for all, because one may differentiate the known $E_i$-functions to arrive at a set of consistency conditions. Let us for simplicity assume that the functions $E_i=E_i(q)$ do not involve generalized velocities $\dot{q}^i$, accelerations $\ddot{q}^i$, and so forth. Then we may assume that the Lagrangian $L$ does not depend on time derivatives of $q^i$ as well. So the question becomes if
$$\tag{4} \frac{\partial L}{\partial q^i}~=~E_i ? $$
We can collect the information of the eoms in a one-form
$$\tag{5} E~:=~E_i ~{\rm d}q^i.$$
The question rewrites as
$$\tag{6} {\rm d}L~=~E? $$
Hence the Lagrangian $L$ exists if $E$ is an exact one-form.
III) However, the above discussion is in many ways oversimplified. The eoms (1) do not have a unique form! E.g. one may multiply the given $E_i$-functions with an invertible $q$-dependent matrix $A^i{}_j$ such that the eoms (1) equivalently read
$$\tag{7} \sum_{i=1}^n E_i A^i{}_j~\approx~ 0. $$
Or perhaps the system variables $q^i$ should be viewed as a subsystem of a larger system with more dynamical or auxiliary variables?
Ultimately, the main question is whether the eoms have an action principle or not; the particular form of the eoms (that the Euler-Lagrange equations spit out) is not important in this context.
This opens up a lot of possibilities, and it can be very difficult to systematically find an action principle; or conversely, to prove a no-go theorem that a given set of eoms is not variational.
Best Answer
Introduction. It is well-known that the stationary solution to a simple harmonic oscillator (SHO) (with Dirichlet boundary conditions) is not a local minimum but a saddle point beyond the first caustics, i.e. if the lapsed time $$ \Delta t~:=~t_f-t_i~>~ \frac{T}{2}\tag{1} $$ is more than half the period $T$ of the SHO, cf. e.g. my Phys.SE answer here.
OP is essentially asking the following interesting question.
Answer: No, not necessarily. A counterexample is a system of infinitely many SHOs, with periods $T_n\to 0$ for $n\to \infty$. For any finite $\Delta t>0$ the highest modes would then be beyond their first caustics, and hence saddle points.
Such a system can e.g. be realized by a vibrating string of length $L$ with Lagrangian density ${\cal L}~=~\frac{1}{2}(\partial_t\phi^2-\partial_x\phi^2)$, which has infinitely many overtones.