Sample selection through clustering
Clustering will be much too expensive for your purpose (most are O(n^2), and the good ones like HAC may even be O(n^3) - you won't be able to run them on 300k instances). Also beware of the prerequisites of the various algorithms - they may not be applicable to your data, or the results may be as bad as random! Also, clustering algorithms may behave rather unpredictable, and will profuce unbalanced data sets. It would not be unusual if 99% of your data ends up in the same cluster, while other clusters are almost empty (or even empty!)

I would consider first to remove all duplicates and maybe near-duplicate records (ignoring identifiers, of course). These algorithms are much more scalable and tolerate more data types. That may already be enough to achieve your goal of data reduction.