What is the importance of memory depth when selecting a digital storage oscilloscope?
It depends on what you are using it for.

In general memory depth allows you to capture a larger time slice of the signal at the same sampling rate

Some applications:

Large memory depth allows you to sample a low frequency signal at a much higher sample rate and still catch the entire signal, this allows you to analyze transients and small features in the signal that would be lost to Nyquist at lower sampling rates.

It also allows you to use a lower sampling rate and acquire for longer, which may seem pointless to you, but it's not uncommon in science (speaking from the POV of an atomic physicist) to use a scope as a general purpose ADC/data acquisition device, with 14m points you can store minutes of data at kHz sampling rate without resetting the acquisition system (and dealing with the inevitable gap in data that causes), compared to a few seconds with 12k points. This can be very useful when recording, say, the decay of an radioactive source with timelines on the order of a minute. With a larger memory depth you can also sample at larger frequency for the same time slice, giving you better resolution.

Whether or not this is important to you depends on what you will be using the scope for. Personally, in my field of work, signal frequency is relatively low and it's more useful to have a high memory depth at the cost of slightly lower sampling frequency. 

I would take the fact that Tektronix's lack of memory depth is basically indicative of their low-end model compared to the upper-middle-of-the-line Rigol offering. Basically Tektronix is more expensive, you pay for construction quality, precision, calibration, warranty, and SNR of their ADCs. You also pay for the name. 

Note: Their DPO series two-channel 100&nbsp;MHz offering is only slightly pricier for 1M sample points; it was my impression that the TDS is an old design (I still use the TDS540, great scope) that has had a few facelifts and is delegated to the budget category.

Not to speculate on their designs, but it not unfeasible that the older design of the TDS uses discrete ADCs and standard microcontrollers for data acquisition, vs. a custom ASIC in the new models which could be easier to expand the memory for.