Paired t-test with small standard error I am comparing two algorithms applied to all frames of a video clip. To evaluate the result I am doing a paired t-test analysis, i.e., I am subtracting the algorithm scores for each frame and then doing a regular t-test on the resulting diff population. 
My problem is that because the number of frames is large (500+) my standard error, s / sqrt(n), is so small that even when I run the same algorithm on the video twice, my statistical analysis gives me the result that mu != 0 although the x_bar of the difference are in the order of 10^-2 (score range is [0, 1] and thus the diff range is [-1, 1])
What is the best way to blunt the analysis? Random selection from the population? 
 A: To follow up on the comments, classicaly, for a large dataset, measuring effect size tends to be important. By effect size I meant measuring how much algo A is better than B. You can look up for example what is cohen's d and compute its confidence interval using boot package with r (or bootES which seems dedicated to this task). For large dataset, significance is easily reached with small effect size so this need to be checked to complement your analysis. 
But here, non-independence is quite problematic. Maybe this is why the same algorithm has "significant" difference with itself (which should not occur in normal condition, even with a large dataset). The problem is even more dramatic if the processing previous frames also influence the processing of the current frame. Moreover, what I think you want is to say something in general on the quality of your algorithms which is not tied to a specific video clip. Your proposition in the comments which consists to manually reiterate your t-test on various clips seems to miss the point that this generalization problem is the point of statistical testing.
I would suggest to use many video clips, even very short ones if you have computational limitations in order to have at least more than 20 clips. For each of this clip, compute your mean score. If your are confident that your mean score follow a normal distribution, use a t-test, else a Wilcoxon signed-rank test. 
