Unsupervised Clustering high dimentional data not having estimation for K I have a dataset (all numerical) of 50K records containing 500 features. we are trying to find fingerprints. Meaning that we would like to cluster the data and report one of the nodes in each cluster as representative of that cluster (meaning that each node in that cluster is mostly similar to that representative compared to any other node in other clusters). So we won't have any noise (meaning that all nodes should be represented). I have done K-means, Kmedoids, hierarchical, dbscan, hdbscan, etc. Each having their own issues. 


Kmeans doesn't report one of the nodes as center for the cluster but the center point which might not be one of our nodes. So we switched to Kmedoids. which the results are too dependent of the initial seed. Also not knowing K is another problem. 
Then we used elbow method to find K. But since not sure what is the upper limit for K, the plot is not very Elbow-y but more like a gradual decrease. Then we tried Sillouette0score method and I got WAY too big number for clusters (something over 200 which doesn't seem right to the field expert). Same problem with the number for K generated by Affinity Propagation (too big of K). 
Since we have tens of thousands of data, Meanshift doesn't relly work properly. Also HDBSCAN reports 264 labels which again seems unreasonable. 


I would like to try some dimensionality reduction methods for this data. But not sure what would work well. tSNE is too focused on visualization which doesn't seem best fit for our use. Any advice would be VERY appreciated.
I point out several things first:


You have an unsupervised problem so the first to know is don't search for The Right Answer. There is no right answer and you take the best you get acording to some pre-defined criteria!
not knowing K is another problem: This is one of many questions in unsupervised learning which do not have any answer! All those methods like elbow are just heuristics.
Kmeans doesn't report one of the nodes as center for the cluster: K-Means can be modified to do so. The simplest trick is to find the closest neighbor of final representatives from the data point and set them as representatives of clusters.
Some methods that you mentioned like K-Means and Sillouette assume gaussian clusters. If your clusters are not properly compact and well-separated, then they mislead you.


After these, let's have a look at your problem. Try to get an insight about your data with visualization techniques. tSNE is pretty sensitive to its parameters and needs more investigation. Start with PCA, KPCA or LLE to get some idea about data. In case they didn't give you a proper embedding, then go for UMAP. UMAP is also sensitive on parametrs but less than tSNE and it's pretty faster. It will give you more compact clusters if it finds any which is a bless for your work. At the end if none of them worked maybe try tuning tSNE parameters and see if you can find a good embedding.

On top of UMAP or tSNE you can try your clustering alorithm and it will be a logical pipeline for your problem.

Good Luck!