Maximally dissimilar subset Given a N-dimensional similarity matrix, is there an efficient way of finding the subset of size M<N that is maximally dissimilar?
(I guess that the notion of maximally dissimilar is not completely well-defined, so let's say I take as an objective function the sum of the similarity matrix.)
 A: The quadratic knapsack problem
This is a special case of the 0-1 quadratic knapsack problem (QKP). In the general form of the problem, we have a set of $n$ items, each with a value and weight. We also have an additional value for combining particular pairs of items. The problem is to select a subset of items that maximizes the total value, without exceeding a given weight limit. The problem can be written as:
$$\max_{x \in \{0,1\}^n} \
v^T x + x^T V x
\quad \quad \text{s.t. }
w^T x \le W$$
$x$ is a binary vector indicating which items are selected. Vector $v$ gives the value of each item. $V$ is a matrix where $V_{ij}$ gives the additional value of combining items $i$ and $j$. Vector $w$ gives the weight of each item, and $W$ is the weight limit.
Formulating the maximum dissimilarity problem
Your problem can be formulated as an instance of the 0-1 QKP as follows. Set the weight of each item to 1, and the weight limit to $M$. This means we will select $M$ items. Set the value of each item to 0, as we only care about the interaction between items. Set $V$ to the dissimilarity matrix. This means we will try to maximize the sum of dissimilarities between selected items.
Solving the problem
The 0-1 QKP is NP hard, so an efficient (polynomial time) algorithm that can solve all instances probably cannot exist. If the problem is only of moderate size, it can be solved using exact search methods like branch-and-bound, which is more efficient than brute force search. However, finding an exact solution is intractable for larger problems. In this case, it's necessary to resort to heuristic search and/or approximation algorithms. The Wikipedia page gives an overview of some of these methods.
