How to optimize cohort sizes to reduce pair-wise comparisons?
There is a better way if I understand your question correctly. Here is the algorithm I propose:


Initialize a 'window' list and a 'pairs' list
Sort your data on birthday from old to young (or the other way around)
Loop over your rows and keep track of all the rows that are still in the last three years since your current row. When you get to a new row, throw out rows that are now more than three years apart, add the current row together with the rows in your 'window' to your pairs set and add current row to your 'window'.


This means you only iterate over your main list once, and if you implement your 'window' list properly (like a linked list for example) you don't need to do a lot of looping in that regard either. You also get all the pairs only once as a by product. Plus you actually get all the pairs, while with your binning approach you get missing pairs around the bin edges (if you don't overlap).

If you use the overlapping binning approach I think you should have bins of 6 years width and the borders shift 3 years each time, that way all true pairs are in at least 1 bin together, and there is the least amount of unwanted pairs.