According to my understanding:
If these two are correct, how can the force of static friction, determined by a force normal to the surface, be directed tangential to the surface and orthogonal to the normal force?
Re. "two orthogonal forces aren't related and two orthogonal vectors don't affect each other"
Your equation $F_s = \mu_s F_n$ is not a vector equation. $F_s$ and $F_n$ are both scalars. If they were vectors, and were orthogonal, the equation would be mathematically incorrect.
There are two different things here that need to be firmed up:
And as you might guess, given the second point, friction is actually very complicated, and so you should wonder "well then why can we describe it by such a cute linear equation"? And you'd be right to be suspicious. The simple linear equation $F_\mathrm{fric} = \mu F_\mathrm{norm}$ is just a simplistic model. It works okay in some limited circumstances and as long as you don't need too much precision. Realistically, friction can indeed be much more complicated, and is best figured out by empirical experiment and measurement, than derived from theory.
Moreover, if you guessed that the effects described, since they involve things bending and breaking, actually modify or damage the surface, you're right! We call this "wear". It's why that sandpaper works, it's why bearings need to be periodically replaced, it's why a nail file works, it's why that if you fall on a road while moving you get road rash, part of why clothes eventually fray from repeated rubbing and use, etc.
Finally, if you think that something interesting might happen if you did have absolutely perfectly geometrically compatible surfaces, e.g. two pieces of metal of the same type, hyper-pure, and surfaces totally flat down to not even a single atom's deviation, you'd be right! Indeed, upon contact the same thing occurs but now over the entire surface: every part bonds, and the two pieces of metal literally merge with no effort into a single contiguous piece, exactly as you'd expect from the notion of attractive forces! It's called "contact welding". It also needs to be done in vacuum, because any air molecules in between will still frustrate the surfaces from perfectly contacting each other. Welds formed this way can be some of the best you can get, but it's very limited in applicability precisely because of the geometric compatibility requirements. Typically one will still need some applied pressure to get a good weld because of this, to deform the surfaces the "last bit of the way" and make them contact each other completely.
Two orthogonal vectors $\vec a$ and $\vec a_{_{\perp}}$ may not be additively related, sure. A linear combination is not possible: $$\vec a\neq k\vec a_{_{\perp}}$$
But we could easily imagine a simple linear function that did this:
$$f(\vec a)=k\vec a_{_{\perp}}$$
Imagine that a rough surface is such a function - that the physical phenomenon of "friction creation" is such a function. A function that takes the vector and converts it into a perpendicular version of itself - times some constant.
The resulting vector $\vec a_{_{\perp}}$ happens to be $k$ times shorter than the original $\vec a$, so:
$$|\vec a|=|k \vec a_{_{\perp}}|\\ a=k a_{_{\perp}}$$
This does not say that vector $\vec a$ equals vector $k \vec a_{_{\perp}}$, only that their magnitudes are equal. And now imagine that we see this behaviour in the physical world and that we rename the parameters involved and write:
$$F=\mu n$$
Again, not a vector relationship. It would be wrong to write: $\vec F=\mu \vec n$. Rather, just a scalar relationship.
So, mathematically, nothing is wrong with the formula: $F=\mu n$. The only question left is why the physical world happens to behave like this?
Imagine a rough surface as full of peaks and valleys at the microscale (microscopy image here from this source). When two surfaces like that come into contact, one will "fit into" the other by having it's peaks falling into the opposite valleys etc. In this fitted position, the touching material may adhere with different weak or strong bondings.
In order to start sliding one surface over the other, you must rip that surface free from the other. You must break the adhesion bonds and must lift the surface peaks out of the valleys. This requires some force. We call that force friction.
Naturally, the harder the surfaces are pressed together - the larger the downwards force $\vec n$ - the tougher it is to rip them apart again, so the larger is $\vec F$. Those two forces happen to be proportional in magnitude, because all other factors (like contact area, speed etc) happen to cancel out.
At very high normal forces or very soft materials, parameters like the contact area will not cancel out. In those cases, the proportionality doesn't hold and $F\neq \mu n$. The relationship $F= \mu n$ counts for small normal forces.
NB: Note that that there is a difference between static and kinetic friction. When you write static friction as $F_s=cF_n$, the be aware that the general low-normal-force relationship should rather be written as:
$$F_s\leq cF_n$$
This relationship only turns into $F_s=cF_n$ right at the limit before the static friction cannot hold anymore.
For low-normal-force kinetic friction the equality is always true, though:
$$F_k=c_kF_n$$
The 'force of static friction' is not a vector per se, it is a limiting value of the tangential force that can be applied without breaking the bond between 'two objects' when those objects are in contact (basically, glued together with a very weak glue). It is a scalar, not a vector.
So, despite the fact that a normal force does not provide any symmetry breaking to generate a 'friction force' tangential vector direction, it does affect the surface/surface bond strength, in shear stress conditions.
The consequences of this, include the impossibility of dissipating energy with the static friction: when taking a dot product of displacement and force, the displacement implies sliding friction. That is why ball bearings (which roll, but do not slide) are so energy efficient. Also, it means that the best ball bearing lubricants are very different from sliding-bearing lubricants.
Given two surfaces which on the microscopic scale are "rough" you might expect that pushing them together harder (the normal reaction forces) would make it more difficult for them to slip relative to one another (the tangential frictional forces) as it more difficult to move the "hills" on one of the surfaces across the "valleys" and "hills" on the surface.
two orthogonal forces aren't related and two orthogonal vectors don't affect each other
This wording isn't very precise. I can think of some ways orthogonal vectors can be related. For example, If I apply a force $\mathbf F$ tangent to a disk at position $\mathbf r$ relative to the center, then $\mathbf r\times\mathbf F=\mathbf\tau$ gives me the torque $\mathbf\tau$ about the center of the disk, and all three mentioned vectors are orthogonal. I would say these vectors are related via the cross product, and both $\mathbf F$ and $\mathbf r$ effect the torque $\mathbf\tau$. To drive this home further, we have, for example, $$\tau_x=r_yF_z-r_zF_y$$ So the x-component of the torque is related to the other two components of the other vectors (Similar expressions can be written out for the other components of the torque).
I think what this statement comes from is what introductory physics students hear about projectile motion: horizonal forces don't influence vertical motion, and vice versa. This is true, because $F_i=ma_i$, where the subscript $i$ represents a component ($x$, $y$, or $z$) of the vectors. This is very helpful for problems where we break up the forces into components, but as we have seen above, this doesn't mean that orthogonal vector components of different vectors can't be related.
So onto friction$^*$, if we have an object on a horizonal surface, there really is nothing wrong with having $$f_x=\mu N_y$$ Or, if we want to be more general, $$f_{parallel}=\mu N_{perpendicular}$$
But since friction is always parallel to the surface, and the normal force is always perpendicular to the surface, we just write $$f=\mu N$$
No problem at all. Note, this is not the same thing as writing $\mathbf f=\mu\mathbf N$, which is not a true equation and might also be adding to your confusion. If you want to use the vectors, you would write $\mathbf f=\mu N\mathbf{\hat f}$ where $\mathbf{\hat f}$ is parallel to the surface and $N$ is the magnitude of the normal force.
$^*$ Unlike other answers that go into detail about why this simple friction model makes sense (and a lot of these answers seem repeat information already posted in answers before them, but I digress), I will not discuss the microscopic details here. Your question is purely about the vectors and not about the physical mechanics behind it.
