Key trick is LOCAL outlier rejection. You don't take the median of the global dataset, you take the median of a subset of frames. Then you do it to a subset of results, and so forth until you get a pretty image. Then you can highlight problem areas and go back and try to sample them from different data, depending on how much you care about that. An incidental benefit of this is that it lets you dramatically speed up the job by throwing CPU cores at it, if that's something you care about.
(Lots of relevant academic papers for after that.)
The problem encountered in the article is that 2100 frames gives 22.4 MB per frame, which napkins out to 5.8 gigapixels uncompressed. For reference, at 30 FPS that would result in 70 seconds of continuous video. Using high-res stills is going to balloon your storage cost & processing time, which has nothing to do with underlying problem.
A good workaround if you want a high-resolution result would be to do processing at a reduced resolution, then upscale from there. E.g. if you drop resolution by 1/4 for processing, you could take the output and for each pixel find the best matches in the source data and sample a larger window from those to get a full-resolution result.
Or you could use one of those nifty video super-resolution algorithms that have been popular in recent computer vision papers. Depending on what you chose to do when you captured the data, and what you feel like implementing.
Times Square is still problematic, mainly because it has persistent crowds during many times of the day. People move out of the way, crowds don't unless there are gaps (which may be inserted due to e.g. stop lights, transit arrival times). Best advice there is to catch it when the traffic is less dense, or when it's disrupted (movie filming, accident, random variation).