Where do we get our sense of perpendicularity?

In general relativity, the metric can always be chosen locally euclidean by selecting an appropriate coordinate system. Locally euclidean means $g^{munu}(x_0)=eta^{munu}$, and the Christoffel symbols ${Gamma^mu}_{kappalambda}(x_0)=0$. Hence your question reduces to one about the euclidean (/lorentzian) metric $eta^{munu}$. The answers you can find in the field of knowledge of "euclidean geometry". I guess that is taught in school.

For example, you can construct an orthogonal line to another line, by choosing two points on the latter line, draw two intersecting circles with equal radius around them, and then connect the intersection points. Et voila: you get the orthogonal line. Since this is a physical experiment, and it is based on euclidean geometry, you have what you asked for. I think it won't get more intuitive than that.

In your other question ( Is simultaneity in SR merely an artifact of coordinate systems? ), I gave this answer ( https://physics.stackexchange.com/a/638018/148184 ).

In the Minkowskian case, the tangent line [hyperplane] to the unit-hyperbola [unit-hyperboloid] defines spacetime-perpendicularity: given a timelike vector, output the tangent line along which a spacelike vector lies that is perpendicular to it. Physically, the inertial observer along the timelike vector regards the spacelike vector as a purely-spatial displacement in her frame. For all events on the tangent plane, those events are simultaneous according to that observer.

Note that when we wish to determine the velocity of a particle, and we write $vec v=frac{Delta vec x}{Delta t}$, the ratio of the "purely-spatial component" to the "purely-temporal component" as measured in our frame of reference, it better be that these components [of a displacement vector along the particle worldline] are spacetime-perpendicular.... otherwise we get the wrong answer because it is as if we are mixing measurements in different frames of reference.

Instead of spacetime, one can consider energy-momentum space in special relativity.
The 4-momentum of a particle is a timelike-vector.
If we decompose that 4-momentum into two perpendicular parts,
one part is purely-timelike in our frame and is called the relativistic-energy,
and the other part is purely-spacelike in our frame and is called the relativistic-momentum.
Again, these components better be spacetime-perpendicular.

(From my answer to Why are the coordinate axes of a moving frame $K'$ tilted in spacetime diagrams? )

Again in the Minkowski case, one can consider a "causal diamond" of two timelike related events P and R (with P in the past of R), defined as the intersection of the future of P with the past of R. The segment FG (the other diagonal of the diamond) is spacetime-perpendicular to PR. As above, if PR is a segment of an inertial observer's worldline, then FG is spacelike and is spacetime-perpendicular to PR and is a set of events simultaneous according to that observer.

Experimentally, if P sends a light signal (say with the image of the clock-face at event P) that is somehow reflected at events F and G and is received at a common event R, then F and G are simultaneous according to PR... the segment FG is spacetime-perpendicular to PR. If another event H (on light-signal PG) reflects the signal, it won't be received at event R. Then FH is not spacetime-perpendicular to PR... and so events on FH are not simultaneous according to PR.

---

For an example with a Euclidean metric, consider uniform circular motion.
Since the velocity vector is perpendicular to the central force, the magnitude of the velocity is unchanged. Expressed a different way, that central force isn't doing work ($int vec Fcdot dvec s$) on the particle.

In an elliptical orbit, the central force (from a focus) is not always perpendicular to the velocity vector of the orbiting particle. Thus, the speed of the orbiting particle varies in the elliptical orbit.

---

Note that one can use the polarization identity to "measure the dot product of two vectors": $$vec acdot vec b= frac{1}{4}left( (vec a + vec b)cdot (vec a + vec b) - (vec a - vec b)cdot (vec a - vec b) right). $$ So, we don't need a "protractor" if we can measure lengths of the vector sum and difference of $vec a$ and $vec b$.