Distance between very large discrete probability distributions
Yes, plenty.

Get the book "encyclopedia of distances".

For example, you can use Histogram Intersection distance. Since your data is already normalized, that reduces to Manhattan distance, if I am not mistaken. Yes: this can be appropriate for distributions.