How many signals do you need to capture and analyze? Be sure to take into account all of the buses and signals that you must acquire simultaneously. A logic analyzer's channel count maps directly on a one-for-one basis with the number of signals that a user plans to capture.
Because digital-system buses come in a variety of widths, there's often a need to probe other signals—clocks, enables, and such—while the entire bus is being monitored.
How much time do you need to acquire? This will govern the memory depth required, and it's especially important in asynchronous acquisition. For a given memory capacity, the total acquisition time decreases inversely as the sample rate increases. For example, the data stored in a 1-Mbit memory spans 1 s when the sample period is 1 µs. The same 1-Mbit memory spans only 10 ms if the sample periods fall to 10 ns.
Acquiring more samples (time) increases your chance of capturing both an error and the fault that caused the error. When it comes to memory capacity, you simply can't have too much!