By it's nature a stepper motor steps and doesn't move smoothly. The difference in using full steps and 1/8th microstepping should be very obvious. Get it to move the exact number of steps for one full revolution.
Are you sure you have the correct connections to the EasyDriver to select the different step rates? (I think the EasyDriver defaults to 1/8 microsteps whereas the Pololu A4988 that I use defaults to full steps).
Probably not the main problem, but the delay between HIGH and LOW doesn't need to be as long as 4 millisecs. I think the Allegro chip on the EasyDriver requires a minimum pulse width of 1 microsecond. I have used 50 usecs but I know that is overkill.
The delay that governs the speed of the motor should all be between the pulses.
I initially thought a combined delay of 8 msecs would be much too fast but it is not far out if you are using 1600 steps per revolution and want 4 RPM. Have you tried it at slower and faster speeds?
The problem may be in your power supply. I have the same motor and it works fine with a Pololu A4988 driver board which is very similar to the EasyDriver.
What voltage are you using to drive the motor - the higher the better within the range allowed by the EasyDriver board. Also, of course there needs to be enough current available and the EasyDriver needs to be adjusted to limit the maximum current so you don't fry the motor.
Can you show us a diagram of your wiring - a photo of a clear pencil sketch is fine.
...R