Choosing a distance metric and measuring similarity
It appears to me that what you're looking for in your use-case is not clustering - it's a distance metric.
When you get a new data point, you want to find the 3-5 most similar data points; there's no need for clustering for it. Calculate the distance from the new data point to each of the 'old' data points, and select the top 3-5.
Now, which distance metric to pick? There are options. If you're using SKLearn, I'd look over this page for example of distance(/similarity) metrics.
If your features are continuous, you can normalize them and use cosine similarity; Start with this, and see if it fits.