Pseudovector argument
There is an intuitive argument, but the first thing to do is to take the Poincare dual of B. In 3 dimensions, there is an epsilon tensor $\epsilon_{ijk}$ which is invariant--- it doesn't change under rotations. It has $\epsilon_{123}=1$ and all interchanges give a minus sign, so that the value of $\epsilon$ is zero of two of the indices are equal, and the sign of the permutation to get to 123 if they are all different. The epsilon tensor contracted with three vectors $v_1,v_2,v_3$ gives the signed area spanned by the parallelepiped they form. Because the signed area is the determinant of the matrix of v's put together as 3 columns, it changes sign under reflection of all three coordinate axes.
The fundamental quantity in electromagnetism is $B_{\mu\nu}=\epsilon_{\mu\nu\sigma}B^{\sigma}$, the epsilon tensor contracted with B. This thing is a rank 2 antisymmetric tensor. Because the $\epsilon$ tensor is invariant, an antisymmetric tensor is equivalent to a vector under rotations, but it isn't equivalent under reflections. The reason is that although a vector changes sign under reflections, a tensor doesn't. This is also true of B--- it's a pseudovector, if you reflect a space with a current carrying wire, the direction of B does not reverse.
The fact that B is fundamentally a tensor, not a vector, means that when it is interacting with a particle with velocity v, it can only form a force when one of the indices are contracted with something. The only thing one can contract with is the velocity, so you get $B_{\mu\nu}v^\mu$ as the force, and this is $v\times B$
In relativity, this is seen to be the only natural thing, since the E and B fields together make an antisymmetric 2-tensor, and the four-Lorentz force is this tensor contracted with the 4-velocity. This form is so natural and intuitive, that it does not require a detailed justification.
More physical restatement of the argument
The above is sort-of formal sounding, but it is just saying this: the magnetic field doesn't change sign under reversing the coordinates of space. To see this physically, consider a solenoid of current stretching along the z axis from -a to a, with the current mostly in the x-y plane along each winding, and reflect this solenoid in the x-y-z axes. Reflecting x reverses the current, reflecting y gets it back to where it started, and reflecting z doesn't change the solenoid.
Since the current is the same, B is the same! So the B from a solenoid doesn't change under reflection. So the force on a particle can't be along the direction of B, because force reverses direction under reflection and B doesn't. The force can only be in the direction of a quantity which does reverse direction, and the simplest such quantity is $v\times B$. Under a reflection, v reverses direction and B doesn't, so the Lorentz force properly reverses.
This argument assumes reflection symmetry, which is a symmetry of electromagnetism, but is actually not a fundamental symmetry in our universe. The same reflection argument shows that magnetic charge is not properly symmetric with electric charge, since magnetic charge changes sign under reflection (reflect all the coordinates with the charge at the origin--- the field moves to a new location, but points in the same direction, so the sense of the magnetic charge is reversed). This property means that magnetic monopoles were an early sign that nature is not parity invariant, and may explain why Dirac was not surprised when the weak interactions were shown to violate parity.
The other assumption is that the force is the simplest reflection invariant combination of B and v. If you abandon the idea that the force is linearly proportional to B, there are more complicated combinations that also work to give a reflection invariant force-law. These combinations generally fail to obey conservation of energy.
In order to have automatic energy conservation (and an automatic phase space with the symplectic properties), you should derive your equations of motion from the action.
Hamiltonian argument and gauge invariance
The best argument is from the concept of momentum potential (or vector potential). Like the energy has a potential energy added to it, which is $e\phi$, the momentum has a potential added which is $eA$, where A is the vector potential.
The Lagrangian for the interaction is
$$ mA\cdot \dot{x} $$
Which makes the conjugate momentum $mv + eA$, so that the kinetic energy is $(p-eA)^2\over 2m$ and the potential energy is $e\phi$. The Hamilton equations for this energy give the Lorentz force law. The Hamilton equations are:
$$ \partial_t p = \partial_x {(p-eA)^2\over 2m + \phi}$$
$$ \partial_t x = {p - eA \over m}$$
And combining the equations to a second order equation for the acceleration of x gives the Lorentz force law. The same replacement in the Hamiltonian, $p$ to $p-eA$, works in relativity to give the correct four dimensional Lorentz force law.
The identification of B with $\nabla \times A$ can be justified from the invariance of the equations under adding a gradiant to A. The classically physical part of A is its curl, and this is sensible to identify with the B in Maxwell's equations.
This argument is fundamentally sound, because it doesn't depend on reflection invariance (any argument relying on reflection symmetry is really bogus, since we know this is not a symmetry of nature in any fundamental sense), and is correct quantum mechanically when you interpret the gauge invariance as a freedom in the local phase redefinition of a charged particle wavefunction. It's only drawback is that it requires some familiarity with Hamilton's principle.
