/u/Weed_O_Whirler has covered the relationship between the cardinal directions and the magnetic field of the Earth, but another aspect of your question is basically asking why do we use a coordinate system that (when viewed on a projected map) is a Cartesian coordinate system. At the simplest level, to define a location in an x-y plane, you need two coordinates. You could theoretically define two coordinate axes which are not at right angles to each other, but it would make defining coordinates way more complicated. The simplest solution is to have two orthogonal coordinate axes (and in reality, to have three orthogonal coordinate axes, i.e., elevation) to uniquely define locations. The same logic can be applied to spherical coordinate systems, i.e., why do we define locations with respect to intersections of sets of orthogonal planes with a sphere? Cause it's easier than defining coordinates with a non-orthogonal set of planes and their intersections with a sphere.

It's also worth noting that in most locations, it's actually rare that the sun rises/sets truly due east/west with respect to true north (and the location where the sun set/rises moves because of the inclination of the rotational axis with respect to Earth's orbital plane). Thus, east and west are not defined as such because of the sun, but rather because they specifically are directions along the equator which is orthogonal to the rotational axis. Even if we were on a planet that had a very high inclination (i.e., the orientation of the rotational axis was much closer to being parallel with the orbital plane) it would still make the most sense to define a set of coordinate axes that parallel the equator (and thus are perpendicular to the coordinate axis that parallels the rotational axis).

Getting back to the relation between our coordinate axes and the magnetic field, it would be interesting to consider a hypothetical of early navigation developing on a planet that had a setup like Uranus, which has a rotational axis nearly parallel to the orbital plane but also a magnetic field that is oriented at a high angle with respect to the rotational axis. We define coordinates on Uranus like we do on Earth, i.e., with respect to the rotational axis, but it's hard to know what kind of coordinate system one would develop if you were living on (a habitable rocky planet) that had a similar setup.