The LM386 isn't a preamp. It's a power amp* (for driving a speaker).
I assume you're driving a speaker from the Arduino's output, or from an audio shield?
What happens when you disconnect the amplifier's input from the Arduino? i.e. Is the noise coming from the amplifier or from the Arduino?
If the noise is from the amplifier, it's probably power supply noise. Try a battery temporarily (just for the amplifier, not the Arduino) and if the noise goes away, the noise is from the power supply.
If the noise is from the Arduino, it's probably a software problem (or it could be the Arduino's power supply).
...with maximum gain.
With ~5V peak-to-peak out of the Arduino, you shouldn't need much voltage gain... If you're running the amplifier off of 5V you don't need voltage gain at all... The LM386's default gain of 20 is too much without a volume control. You only need current & power gain. And of course, the noise gets amplified along with the signal so the more gain you have the more noise you're going to hear (if the noise is coming out of the Arduino).
- It's a low-power power amp, but anything that drives a speaker is a power amp. A preamp is used to amplify a microphone or phono-pickup (millivolts) to line level (about 1 Volt).