Since the Lagrangian results in exactly the same equations of motion as Newton's laws, I'd say that based on their agreement with experiment both are on equal footing.
Of course, to get the right equations of motion from Lagrange's equation you have to pick the right Lagrangian, so then you ask how we systematically pick the right Lagrangian.
The recipe in mechanics is
$$\mathcal{L} \equiv T -U \, ,$$
so then you ask how we systematically find $T$ and $U$.
From a purely theoretical perspective, finding $T$ and $U$ is on the same level as picking the forms of various forces used in Newton's law.
The practical difference is that force can be defined in a way that relates it to simple experiments, so pedagogically we start with force.
The question specifically asks if observation, intuition, and physical principles naturally lead to the Lagrangian formulation.
One perspective is that the principle of least action is the phsyical principle of the universe, so from that perspective the answer is "yes".
I wouldn't say intuition leads to the Lagrangian formulation, but I also wouldn't say that intuition leads to Newton's law.
It is quite mind-bending when we first learn that an object uninterrupted by external forces moves at constant velocity.
This is unsurprising given how long it took humanity to figure that out!
What about observation?
Certainly the right observations lead naturally to Newton's law.
Put a feather on top of a book and drop them and you'll see the feather fall just as fast as the book.
Push harder on a cart and it speeds up faster.
The Lagrangian formulation doesn't arise from every-day observations like those.
Still, in the end the Lagrangian formulation definitely can come before Newton's laws.
There's nothing more arbitrary or unfounded in dictating the forms of $T$ and $U$ for various systems than there is in dictating the form of $F$ in those same systems, so the answer to the main question of whether the Lagrangian can be developed without talking about Newton's laws is a definite "yes".
Pick any physical system and we most certainly can describe and analyze it with the principle of least action without ever talking about force or Newton's laws.
In fact, there are lots of non-mechanical systems where Newton's laws don't work at all but the principle of least action works amazingly well (e.g. spin, circuits).
Summary: Dictating that physical systems minimize $\int T-U\,dt$ and dictating how write down $T$ and $U$ for each type of system is no more arbitrary than dictating that physical systems obey $F=ma$ and dictating how to write down $F$ for each type of system.
EDIT: As mentioned in the comments, it is possible (and typical in some settings) to guess the form of a Lagrangian for a system based almost entirely from symmetry principles.
This works even for things like Lortentz invariance; you can derive Maxwell's equations from Lorentz invariance, conservation of charge, and some assumptions about the structure of space-time.
This makes the Lagrangian arguably more general than Newton's laws.
That said, it's also possible to guess the form of the Forces for a system from the same symmetry principles, so it's not always really true that the Lagrangian is really more fundamental.
