Best tools to debug simple digital circuits?
essentially, an oscilloscope gives you a graded reading of the voltage on the line while a logic analyzer will only tell you if it is 0 or "high" (the value of "high" could potentially be 5V, 3.3V or 1.8V depending on your circuit). You will often see that logic analysers have many more channels (lines that can be read simultaneously) than oscilloscopes because of the lower resolution required.

As for a specific device, I have heard great things about the Saleae Logic. It samples at  24MHz; this means it checks if the voltage on a particular probe is high or low 24 million times a second. The software also appears to have some knowledge of the common embedded protocols to aid debugging. I would imagine that 24MHz would be enough for arduino work as the maximum clock speed of the Atmegaxx8 is 20MHz.