Physical intuition for why proper time is an invariant quantity
Let's be precise here. The 'invariance' in question is invariance of the spacetime interval under Lorentz transformations. Lorentz transformations here relate the coordinates of an event as measured by Alice with that of Bob, where they have a boost velocity with respect to each other. As such, Alice measures some time $t_A$ and Bob $t_B$. The transformations do the job of taking you from one observer to the other to see what it's like on their side of the world; it's like saying that Alice puts herself in Bob's shoes or vice versa.
But when you are talking about proper time, you are, by definition, adhering to only one observer: the particle itself. It doesn't make sense to say that the particle is boosted with respect to itself. There is no ambiguity in choosing a reference frame before deciding on performing a measurement, because the reference frame/observer has been chosen, a priori.
Well, let the thing that the two people observe be a clock -- a mechanical clock. If they disagree about the proper time on its worldline between two events, then they also disagree on its physical state at at least one of those events in general. That means that, say, if the two observers and the clock meet at some point on its worldline, then they will disagree about what time it says and all sorts of other details of its construction. That would be a disaster.
Yes, that is a valid way of understanding why the proper time is invariant; it does indeed come from an invariant question.
I am also a big fan of introducing Lorentz transforms by first looking at the transform for small $v$ which essentially sets $\gamma = 1$ and finding just $x' = x - v~t,~~t'=t - vx/c^2.$ This simplified view shows you that trying to compare time differences between things at two different positions is as frame-variant as trying to compare position differences between things at two different times: the distance between Kansas City and Washington is around $\text{1,500 km}$ if you are talking about at one instant of time, but if we're talking about the distance between where Kansas City is and where Washington D.C. is two-and-a-half hours later, then we need to know your reference frame because from my perspective they're still $\text{1,500 km}$ apart, but there's another perspective (an airplane flying from KCI to Dulles) for whom those locations are both "they're right here, outside my window!". This is to say nothing of two other reasonable perspectives, the geocentric non-rotating perspective by which Washington has moved I think $37.5^\circ$ to the East and therefore is $\text{4,700 km}$ away from where Kansas City was, or the heliocentric frame where those two locations differ by approximately $\text{270,000 km}$ apart or so, depending on what time of day it is. You have to be very careful to say "I want the distance between where these two things are right now," in classical physics, to have a number which all of these perspectives can agree on.1
Similarly as we move into relativity we have to become very careful to say "I want the time elapsed between these two events, in the inertial reference frame where they both occurred at the same location," so that both of those events happened "right here", otherwise we will be very confused. This time elapsed is the so-called "proper time" between the events.
As you can see this also becomes a little more difficult in relativity, as we start to disagree on when right now is at remote places. We technically have to say in the co-moving reference frame which sees both of them at rest for objects which exist over long periods of time, and we're permanently unsatisfied if they're not both at rest relative to each other -- or else we can talk about a proper distance between instantaneous events just like we do for the time-separation; then it's in the inertial reference frame where they both occurred at the same time.
In fact special relativity makes these two into disjoint circumstances: events which are objectively separated by distance generally admit reference frames which say "those both happened at the same time" whereas events which are objectively separated by time generally admit reference frames which say "those both happened right here, at the same place." The defining difference is whether light from one event could have reached the location of the other before it happened; and the only exceptions are the "null-separated" frames where light from the one event has just barely reached the other at the time when the new event has happened. These "null-separated" events form the third possibility, "one was objectively before the other and they were objectively not in the same place, but the time elapsed between them and the space difference between them can be brought arbitrarily close to 0 by selection of the right reference frames."