A DSO should have a bandwidth of at least 10x the frequency of the square wave you want to look at. This is because a square wave at, say, 10MHz, consists of a series of sine waves of specific frequency and phase. So there is a 10MHz primary, then odd harmonics. If you capture up to the 9th harmonic, it is a pretty good approximation of a square wave.
Of course, you don't usually need to look at the 16MHz clock signal on your Arduino. But you will be looking at other signals that are derived from it.
And to be more accurate, the DSO bandwidth should be at least 10x the highest frequency content of a rectangular wave.
So a 10kHz PWM signal at 50% duty cycle will have the 9th harmonic at 90kHz. But at 1% or 99% duty cycle, the highest frequency content will be the 9th harmonic of 1MHz due to the very short pulse, or 9MHz.
This is why I consider those kit DSOs to be nothing but toys as the commonly have a bandwidth of 100kHz or less.
Also, the capture rate should be 5x the bandwidth, or faster. Yes, I know, Nyquist sampling theorem, but that is for a sine with no higher frequency content. You will be looking at complex waveforms. And the bandwidth is the point at which response starts dropping off and is down by only -3dB.
In commercial DSOs, it is common to find the sampling rate to be 5 to 10 times the bandwidth. You know if they could get away with more bandwidth, they would.
What Nyquist Didn't Say, and What To Do About It
I would not bother with less than 2 channels. In fact, 4 channel DSOs have come down to under $400, it just doesn't make sense not to save up a little more and get one. I bought the Rigol, buy the 50MHz model and apply a firmware change that makes it 100MHz bandwidth because the hardware is exactly the same. $350 for four channels and four probes.
Oh, yeah, watch out for that little piece of c##p the DSO203 that everyone claims has "72MHz analog bandwidth". Some marketing wonk took the specification for 72Msps sampling rate and called it bandwidth. The real bandwidth for it is about 3.5 to 4MHz. My calculations and Electronic Design News tests agree on that. Not bad, but limited to square waves at 1/10th of that.
Knowing that, the latest one shares a 144Msps sample rate between four channels. So 36Msps at 3.5MHz bandwidth is just about right. Fine for the Arduino's analogWrite() PWM function that runs at 490Hz or 980Hz, depending on the particular model of Arduino. Or for audio. Forget troubleshooting a switch mode power supply with it, though.