Digital vs. Analog: I've a preference for digital, because I'm often looking for transient stuff, and I like being able to stop on a trigger and really look at the signal. This is somewhat dependent on the work you do, but I think it's mostly an artifact of what you are used to. I came up working with digital scopes (and scope/logic analyzer hybrids), so that's what I like.
Bandwidth: Just make sure it's high enough for what you want to look at (I do old arcade gear, which tops out in the < 20 Mhz range, so I don't need a lot of bandwidth). Remember that this is the ANALOG bandwidth - not the sampling rate of a digital scope.
Sampling rate: Digital scopes only, of course, but with digital scopes remember that the sampling rate is NOT inherently related to the bandwidth. It's entirely possible to have a scope with a high bandwidth, but a sampling rate barely able to meet Nyquist on that bandwidth.
Memory depth: Again, digital scope only, but important. Especially important is to look for shady specs like only being able to sample at full rate with a part of the memory buffer. This trick is kind of common and quite annoying, because it makes comparing the sampling rates of different scopes quite difficult.
Specialty items: There are a lot of 'USB scope' things out there these days. BE CAREFUL! Especially if they say 'unlimited buffer', you want to look closely - those scopes turn out to be sample rate limited to however fast the USB bus is on your computer. In an optimal situation they should be able to meet their stated sample rate, but if something (driver issue, competing device, whatever) slows your computer's USB bus down, then your sample rate can drop. On the other hand, they are usually quite cheap.