The higher the frequency the better... 20MHz is minimum for arcade work... 40 is better... 60 is even better... etc.
Dual channel at a minimum. If you have 4 channels you can watch signals going into a logic gate and see what the output is.
XY mode is a MUST if you're doing any work on vector games.
Brands don't matter, but you really can't go wrong if you stick with one of the bigger names - except I wouldn't have a Sencore scope if it were given to me. Huge POS brand for scopes.
Tektronix, HP/Agilent, Hitachi, Philips, BK Precision, etc... They are all fine. Cheapo Chinese scopes? I'd stay away from them personally. There are plenty of ppl happy with their Rigol scopes, but all of my scopes are Tektronix.
RJ