NavList:

Lines of longitude and latitude always meet at right angles.  Your issue is that (other than the Equator) circles of constant latitude aren't great circles; their centers are on the earth's axis but aren't at the center of the earth.  The sides of a spherical triangle all need to be angles measured from the same point, i.e. the center of the earth, so all sides need to be great circles.

You'll note that, even if both your starting point and destination are at the same latitude, the great circle route still involves journeying to a higher latitude.  Following a great circle, you'll first aim at a compass heading closer to the pole, and then spend the entire journey gradually turning away from the pole.

If it helps you any, I think you might be trying to apply what you know about flat triangles onto a curved surface.  For a flat triangle, all three angles add together to exactly 180°, and knowing that one of the angles is 90° means you also know the other two angles are complements, the sine of one is the cosine of the other, etc.

In spherical triangles, knowing one angle is 90° helps simplify some of the math, but not as much as it does with flat triangles.  In a spherical triangle, the sum of the three angles is always greater than 180°, so knowing that one is 90° doesn't immediately tell you about the other two angles.  All three angles (and all three sides) could be 90°.  In a sense, a great circle by itself can be considered a "triangle" with all three angles equal to 180° (for a total of 540°).

So don't get too hung up on making things square.  On a curved surface, your squares will have four equal sides or four right angles, but not both.