Is it strange that there are two directions which are perpendicular to both field and current, yet the Lorentz force only points along one of them?

The universe is not preferentially selecting one direction over another. The fact that it appears that this is happening is an artifact of how we represent the magnetic field.

It is well-known that the existence of magnetic forces can be inferred from a Lorentz-invariant theory involving electric forces. For example, see this answer.

The magnetic force so derived necessarily has the property that parallel currents attract while antiparallel currents repel.

The magnetic field can be thought of as being the field that needs to be introduced into the theory in order to give a local description of this attraction between parallel currents. It is therefore necessary for the Lorentz force law to be written in such a way so that it gives the correct direction for the magnetic force between two currents. Otherwise the law would violate the observed Lorentz invariance of our universe. A law itself does not determine what actually happens; that can only be determined by experiment.

Because the direction of the magnetic field is assigned through a right-hand rule, a second application of the right-hand rule is needed in the Lorentz force law in order to get the correct direction for the actual force between the two currents. If the magnetic field direction were assigned through a left-hand rule, the Lorentz force law would also involve a left-hand rule. In neither case does the universe enforce an arbitrary choice of one over the other. We are simply describing the phenomenon in a way that requires us to put in the rule by hand in order to get the correct result.

This contrasts with the situation with weak interactions, which really do violate parity symmetry.

The magnetic field is not a [polar] vector, but a pseudovector. In fact, the cross-product of a vector (e.g. Velocity) and a pseudovector (Magnetic Field) is a [polar] vector (e.g. Force).

In a more abstract view, the magnetic field is better represented by a two-form or by a bivector [depending on your abstract point of view]. In 3 spatial dimensions, these abstract objects can be mapped to a pseudovector. In any case, it is this additional sense of orientation that prefers one "perpendicular" direction over the other.

You can see this distinction in the way the electric and magnetic fields are represented in the field tensor. The magnetic field components are in the entries of an antisymmetric 3-by-3 submatrix.