find most dense neighborhood of points in high dimensional space

If you're looking for the metric to use to determine how close together (or not) some points in a set are, I think there are a few obvious ones to consider:

1. Diameter, from point-set topology: Look at all pairs of points in the set and take the maximum distance $epsilon$ between any two of them. Call that the "diameter" of the set. In other words, the widest the set is in any direction is $epsilon$. This is easy to compute and might get you what you want.

2. Find the smallest number $epsilon$ so that there's a ball somewhere of radius $epsilon$ that contains your entire set. It's isn't obvious how to compute this in real life, but here's an equivalent way to do it: pick a really small number $epsilon$ and draw a little ball of radius $epsilon$ around each point in the set. When $epsilon$ is sufficiently small, these little balls don't overlap at all; as you increase $epsilon$, though, they start to overlap a little, and, eventually, all the balls will overlap at some point. Freeze it there and grab that $epsilon$ and call it the size of your set. This is a little hard to compute, but it's the version of set distance used in the original definition of persistent homology, so it's certainly in use in big data analysis already; see here for a nice visualization.

3. A variation on #2, much easier to calculate and now in use as one of the standard simplifications of persistent homology: pick your $epsilon$ really small so the balls don't overlap at all and gradually bump them up; as the balls start to overlap, count the number that overlap together, ie, that form a continuous region. Do this until all your balls in the set overlap, freeze it, and take that $epsilon$ as the size of your set.

In terms of your actual question, I think all of these will require you to take a small $epsilon$ and start bumping it up and looking for n-element sets of size at most $epsilon$; #1 is probably the easiest to calculate and might give the results you're looking for, although you can certainly see why #3 is in use for this purpose, too.

Look into anomaly detection algorithms. Scikit-learn has a variety of built-in ones in its outlier detection module. Finding 30 most similar points among 500 is the same as finding 470 outliers. Most of these algorithms have a parameter contamination which specifies what fraction of your dataset you generally expect to classify as outliers, so manipulating the value of this parameter can possibly give you what you want to achieve.