Well a scope with a proper trigger counter is nice, most have that and while not a great counter it doesn't take any desk space or cost any money.
Having automatic peak, peak-peak and RMS measurements is handy, too, esp. RMS since that's not easily worked out from for complex waveforms
Deep memory is a must for some things, others will never notice it
Filters (including averaging). I wish more scopes had arbitrary filters (LPF/HPF/BPF), but most have at least selectable bandwidth, so that's a start. A 500 MHz scope would be quite useless for many things if it didn't have a LPF option.
FFT is handy for similar reasons as the trigger counter, although you'll get more from the DSOs' AFE if you export the waveform data and use some PC based software to analyze it
Decent resolution color screen. A scope is about seeing things. Not much to see with a crap screen.
Intensity grading should be standard.
Unnecessary (IMHO): decoding (most scopes can't decode much, and it's completely useless on 2 ch models), front panel presets, auto set, unnecessary built in help, stupid dials that are hard to adjust (heeeellooo, hantek 5000 series)