If you will be using the oscilloscope to analyze digital signals, specially serial data then memory depth is extremely important.
Other situation where memory depth is important is when you have two spaced event and you need to analyze both in detail. If your oscilloscope does not have enough memory depth you have to choose to see an overview of both events at a low resolution or analyze just one of them.
I have a Rigol DS1052D with 1M points memory, and the main reason I choose it over the other candidates was the memory depth.
Between the Tektronix and the Rigol you suggest I would not hesitate in buying the Rigol. Their instruments are well built with a very professional look and feel, not to mention the set of features you can not find on other brands on the same price range.
Rigol has a video explaining the importance of memory depth on an oscilloscope here.