You describe order of events in Minkowski spacetime exactly as you do for Newtonian physics with one difference: the events can only be well ordered if they lie in each other's past or future light cones. If the events have this relationship, then their order, as told by their time co-ordinates in any of their reference frames, is NOT observer dependent, even though the time intervals between them are observer dependent.
Indeed you can take this fact as the reason special relativity imposes the universal speed limit $c$. That is, we learn from special relativity that event order is observer dependent. Oh no! How does the principle of causality that causes must always come before their effects and which has never been experimentally seen to be violated survive this fact? Well it can't in general, but if we make the further postulate that events can only be causally linked if they lie in each others future / past light cones and the postulate that no observer can travel at a speed greater than $c$ relative to us, then this new, restricted causality is perfectly compatible with relativity: the order of such events cannot change between reference frames. There are other motivations, such as the requirement of infinite energy to accelerate any massive thing to a relative speed of $c$, but for me this the simplest and most powerful motivation: the speed limit exists to uphold our experimentally observed principle of causality. It's worth also witnessing that only a signatured metric, like the proper time interval, with one timelike co-ordinate can save causality in this way. A Riemannian universe cannot have even a restricted causality principle since in that case the order of all pairs of events is observer dependent.
Technically, this situation arises from the fact that the transitivity sets for the identity connected component of the Lorentz group (the so called, proper (volume form sign preserving), orthochronous (time interval sign preserving) Lorentz group $\text{SO}^{+}(1,\,3)$ for a given event are (1) the sheet of the two-sheeted hyperboloid $t^2-x^2-y^2-z^2=\epsilon^2>0$ that is contained within the origin's future light cone, (2) the other sheet of the same hyperboloid, contained in the past light cone and (3) the one sheeted hyperboloid $x^2+y^2+z^2-t^2=\epsilon^2>0$ contained in the elsewhere outside the cones. The image of an event in any of these sets stays in these sets under the action of $\text{SO}^{+}(1,\,3)$: thus if event $B$ is in the future or past light cone of event $A$, then the sign of the difference $\Delta\,t$ between their two time co-ordinates cannot change under any Lorentz transformation belonging to the identity connected component $\text{SO}^{+}(1,\,3)$. However, if $B$ lies outside the future/past light cones of $A$, then one can always find a proper, orthochronous Lorentz transformation that will change the sign of the difference between the two time co-ordinates.
Proof Sketch on Transitivity Sets
You can prove the above assertions by reasoning along the following lines: let event $B$ be in the future / past light cone of the origin and have co-ordinates $(t,\,x,\,y,\,z)$ where $t^2-x^2-y^2-z^2 = \epsilonˆ2 > 0$. Then $t^2=\epsilon^2+x^2+y^2+z^2>\epsilonˆ2$ where $\epsilon$ stays constant when $B$ is acted on by a Lorentz transformation. Thus we see that $t$ is excluded from the interval $(-\epsilon,\,\epsilon)$. Now act on the event with an element of the form $\exp(s\,X)$, where $X\in\mathfrak{so}(1,\,3)$ and $s\in\mathbb{R}$ varies continuously. Therefore, the time co-ordinate $t$ of the image of the event must move continuously with $s$ and therefore cannot jump the exclusion interval $(-\epsilon,\,\epsilon)$. On witnessing that any member of $\text{SO}^{+}(1,\,3)$ is a finite product of elements of the form $\exp(s_j\,X_j)$, we see that the image of $B$ is path connected to $B$ by a piecewise smooth path defined by each of the $s_j$ varying in turn from the value $0$ to their final, real values. Therefore, the image of $B$ cannot jump over the exclusion interval (which jumping would make the image a discontinuous function of one of the $s_j$).
To deal with the case where $B$ lies outside the future / past light cones of the origin, so that $x^2+y^2+z^2-t^2=\epsilon^2>0$, impart a rotation to bring the co-ordinates of $B$ to the canonical form $(t_0,\,\sqrt{\epsilon^2+t_0^2},\,0,\,0)$. Now find a proper, orthochronous Lorentz transformation that will map $(+t_0,\,\sqrt{\epsilon^2+t_0^2},\,0,\,0)$ to $(-t_0,\,\sqrt{\epsilon^2+t_0^2},\,0,\,0)$; the inverse of this Lorentz transformation then maps $(-t_0,\,\sqrt{\epsilon^2+t_0^2},\,0,\,0)$ to $(+t_0,\,\sqrt{\epsilon^2+t_0^2},\,0,\,0)$ (exercise for the reader).
