How to control 130-size DC motors with an Arduino (seemingly 20A DC motors)

It can be done with interrupts. Attach an interrupt to a timer, so that it fires regularly (say once a milisecond), and use that interrupt to pop the next command off the top of a queue (could just be an array).

Your main loop then just adds commands to this array.

A single Arduino has 14 IO lines, so the number of motors you can control depends solely on the number of wires needed for each motor.

There are dedicated stepper motor driver ICs that are much better and simpler than using a 555 timer. The floppy drive will be using one (maybe embedded inside another chip). They usually accept simple up/down step signals and convert them into the proper sequence of pulses.

Edit

Example code, using the Timer1 library:

#include <TimerOne.h>

void test()
{
  digitalWrite(5,HIGH);
  delayMicroseconds(100);
  digitalWrite(5,LOW);
}

void setup()
{
  Timer1.attachInterrupt(&test,100000);
}

void loop()
{
}

This will cause digital pin 5 to go high then low once every 100,000µS - you see there is nothing in the main loop at all. Just replace the two digitalWrite() calls with the code to step your motors once. You do not need to specify any inter-step delay in that part of the code - that delay is set by the value of 100000 in the Timer1.attachInterrupt() function. To change the speed of the steps, change that value.

1) 31KHz is a much more reasonable PWM frequency than 500Hz. Motors will act like a low-pass-filter and generally give you the DC equivalent of your PWM but with very low frequency PWM that gets dicey - as you've seen. In general, you should increase the frequency of the PWM above the bandwidth of the motor - otherwise it sees a square wave rather than a DC voltage. 31KHz is right in the range of most motor controllers I've seen. You generally want it high but not too high (HF noise may couple into other parts of the circuit, etc.). It looks like you're in a good range with 31KHz.

2) It shouldn't affect those bit rates. The peripherals ought to have their own dividers and scalers and should be driven off of the main clock and not a peripheral timer. I can't speak to the pulseIn function though.