Okay cool.

I take your point. Maybe you are right, but I'd argue that the first option actually applies to gauge theory in the following way:

First, I have to assert that Lagrangian formulations of standard physics are generally simpler than say, Newtonian form. This is because the equations of motion all come from one principle - least action.

Second, I assert that when working with a Lagrangian, it is impossible to derive all the needed physics without introducing gauge freedom somewhere. For a simple example (that is within range of my brain+sources (see footnote1)) Try it with the magnetic field, B.

There is a constraint on B that it must be everywhere divergence free. The easiest way to ensure this is to write the magnetic field as the curl of something. This introduced redundancy in the description but ensures we do not have to worry about the fact that B is constrained to be divergence free (- now there is no alternative!)
Furthermore, there is no way to derive Lorentz's force law from a Lagrangian without adding a gauge freedom term.
-end example

This example is from Susskind's "The Thoeretical Minimum," page 211 (for the case of the Lorenz force law)
This kind of thing generalizes well to differential forms and comes in handy deriving, e.g. Yang Mills, or making sure some particular theory is "manifestly co-variant" - that sort of thing. It makes the thing easier, not harder to properly formulate.

One could build the theory without using a Lagrangian (or without anything "math-mechanically equivalent" like a Hamiltonian) but then you loose the simplicity of the dynamics falling out of principle of least action. This use for least action is universal across everything we currently know about fundamental physical theories.

In sum, I assert it makes sense to go with the first "sensible scenario." ...And that it leads directly to gauge redundant theories just like we have. But of course this assertion of what is easier is subjective (see footnote2).

To get even more subjective for a minute, there are these amazing coincidences, such as the fact that GR looks like E&M, and even more like Yang Mills when they are viewed in this "action oriented" way. -A way that basically requires the use of gauge freedom to get to the correct dynamics. Why turn away from that? Well you would if you found something else simpler and more beautiful. To me, it looks like with gauge theory we have something too amazing, and too pretty, to be a coincidence or to ignore. But hey, if you have something up your sleeve to beat it, don't leave us all out!

Anyway, if you see it differently, all well and good. If you think the above stuff is ...just that... then by all means, teach me better!

This has been fun.

Cheers.

(footnote1)
Further investigation reveals that there appear to be theorems and classification results proved by Cartan, Weyl, and others implying that second order quasi-linear field equations for the metric tensor possessing symmetries and conservation laws of the Einstein equations necessarily arise from a variational principle.
This claim taken from: Gauge invariance, charge conservation,and variational principles, by Manno, Pohjanpelto, and Vitolo
-I wonder what else is out there in this regard?
-I am betting there is more but I really do not know.

(footnote2)
Okay, to try and get past the subjectivity, how about comparing two non-equivalent theories to see how "different they are"?
Could there be some use for gauge redundancy here? Skimming around when I could during a meeting at work I find hints of this idea in
"General covariance from the perspective of Noether's theorems" from Brown and Brading.
http://philsci-archive.pitt.edu/821/1/TorrettiB&B.pdf page 8, footnote.
But again, I surely don't know!