Reducing sample size I have a large dataset (around $ 10^6 $ samples) and an algorithm that will surely choke on that much data.

Suppose that I have removed duplicates and near-duplicates. What are the well-known techniques for reducing sample size without losing too much of the information possibly encoded in the initial dataset?

I thought about using some clustering algorithm (which scales well with respect to number of clusters, possibly BIRCH) and use the resulting clusters to find $ N $ nearest points to cluster centroid. However this feels somehow wrong.
One method would be to take many subsets of your dataset, i.e.
bootstrapping, build your models, perform cross-validation and calculate the average performance.  This is a good explanation of how the amount of data affects the model outcomes: https://stackoverflow.com/questions/25665017/does-the-dataset-size-influence-a-machine-learning-algorithm

Play around with the size of your subsets until you start getting stable results.