If I power my board off the USB and supply the motor 5V from the arduino, it runs.
That suggests your wiring is basically OK.
If I give it Vin, it doesn't run.
You can't use Vin to provide power to external devices when the Arduino is powered from USB.
If I power my board off a regulated 12V wall adapter and supply it Vin, the motor takes about 3 steps and then starts to shudder back and forth.
What is the current rating of the 12V supply? Is the motor driver chip getting hot? I suspect that the motor is drawing too much current for either the power supply or the chip.
If I give it 5V, it takes about 16 steps and then starts shuddering.
The 5V regulator on the Arduino is probably going into thermal shutdown. You are asking it to drop 7V while passing quite a lot of current (because of the motor), which equates to a lot of power dissipation.
If I supply it 3.3V, it runs fine but the arduino heats up to blazing hot. I get that this low voltage means I'm drawing a lot of current.
It's probably the voltage regulator that is getting hot, but not enough to go into thermal shutdown this time, due to the reduced motor voltage.
If the motor runs OK at 5V, why not supply both the motor and the Arduino from a 5V USB adapter?