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? By "strange" I mean 'Is there a reason for this, or is it something we accept as a peculiarity of our universe?'
I see no reason why if magnetic field is in the $+x$ direction and a charge's velocity is in the $+y$ direction, that the force experienced by the charge can't be in either the $+z$ or $-z$ direction, both are perpendicular to $x$ and $y$. The equation for Lorentz force just tells us that it goes in the $+z$ direction, but it seems equally valid that the force would be in the $-z$ direction (I mean there's nothing to distinguish $+z$ from $-z$ anyway, you can turn one into the other by swapping the handedness of your coordinate system). It seems as if the universe is preferentially selecting one direction over the other.
As a practical example, if a current carrying wire is in a magnetic field and it experiences an upward force, why shouldn't it experience a downward force?
 A: 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.
A: 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.
A: 
... there are two directions which are perpendicular to both field and current, yet the Lorentz force only points along one of them

Your statement is correct for electrons and anti-protons. If one do the same experiment with positrons are protons he’ll observe that the move in the opposite direction.

I see no reason why if magnetic field is in the +x direction and a charge's velocity is in the +y direction, that the force experienced by the charge can't be in either the +z or −z direction.

The reason lays in the nature of the mentioned subatomic particles. All they obey the intrinsic property of a magnetic dipole moment and an associated intrinsic spin. The spin does not mean that the particle is rotating, the name points to the macroscopic phenomenon that is known as the gyroscopic effect.
The mechanism behind the Lorentz force is the following. If an electron is under the influence of an external magnetic field it’s magnetic dipole moment gets aligned. Nothing more happens. But if this electron is moving into the external magnetic field the alignment is accompanied by a sideway deflection like in the gyroscopic effect.
As you know any deflection is an acceleration and under acceleration a electron emits photons. This photon with its moment dis-align the magnetic dipole moment again and the cycle with alignment, gyroscopic effect, photon emission repeats until the kinetic energy of the electron is exhausted. So the electron moves in a spiral path or more precise in tangerine slices.
For the positron the process is the same except the direction of the emission of the photons. So 

if a current carrying wire is in a magnetic field and it experiences an upward force,

With anti-matter

it experience a downward force.

A: You just discovered something pretty fundamental about the universe. It is conceivable that there would be a "mirror image universe" in which the laws of physics are exactly the other way around. But that's not the universe we live in.
There is an interesting Feynman lecture one the topic of symmetry - in particular, on the difficulty of trying to explain "clockwise" to someone without any visual aids. See this link
