Just for interest, I point out that it is well-known that for every finite group $G,$ we can make the group algebra $\mathbb{C}G$ into a $G \times G$-module, by setting $a(g,h) = g^{-1}ah$ for all $a \in \mathbb{C}G,$ for all $(g,h) \in G \times G.$ It is easy to check that this representation is multiplicity-free. In fact, calculating the trace with respect to the natural group basis for $\mathbb{C}G,$ we see that ${\rm trace}(g,h) = |C_{G}(g)|$ if $g$ and $h$ are conjugate in $G,$ and $0$ if they are not conjugate. Hence the character of $G \times G$ afforded by this representation is $\sum_{i=1}^{k} \overline{\chi}_{i} \otimes \chi_{i}$, where $\{ \chi_{i} : 1 \leq i \leq k \}$ are the irreducible charactes of $G.$ It is also easy to see directly that the algebra of $G \times G$ endomorphisms of this module is isomorphic to the commutative ring $Z(\mathbb{C}G).$ This way of looking at the group algebra as a $G \times G$-module ( or as a bimodule for $G$) was profitably exploited in modular representation theory by J.A. Green. But in the context of this question, it illustrates that the existence of a faithful multiplicity free representation puts very little restriction on the structure of the group. Notice that if we take the group basis for $G,$ the module may be viewed as a transitive permutation module, and that the stabilizer of the identity element $1_{G}$ is the "diagonal" subgroup $\Delta(G) = \{ (g,g) : g \in G \}.$ It is easy to check that the module is faithful if and only if $G$ has trivial center.

Just for interest, I point out that it is well-known that for every finite group $G,$ we can make the group algebra $\mathbb{C}G$ into a $G \times G$-module, by setting $a(g,h) = g^{-1}ah$ for all $a \in \mathbb{C}G,$ for all $(g,h) \in G \times G.$ It is easy to check that this representation is multiplicity-free. In fact, calculating the trace with respect to the natural group basis for $\mathbb{C}G,$ we see that ${\rm trace}(g,h) = |C_{G}(g)|$ if $g$ and $h$ are conjugate in $G,$ and $0$ if they are not conjugate. Hence the character of $G \times G$ afforded by this representation is $\sum_{i=1}^{k} \overline{\chi}_{i} \otimes \chi_{i}$, where $\{ \chi_{i} : 1 \leq i \leq k \}$ are the irreducible charactes of $G.$ It is also easy to see directly that the algebra of $G \times G$ endomorphisms of this module is isomorphic to the commutative ring $Z(\mathbb{C}G).$ This way of looking at the group algebra as a $G \times G$-module ( or as a bimodule for $G$) was profitably exploited in modular representation theory by J.A. Green. But in the context of this question, it illustrates that the existence of a faithful multiplicity free representation puts very little restriction on the structure of the group. Notice that if we take the group basis for $G,$ the module may be viewed as a transitive permutation module, and that the stabilizer of the identity element $1_{G}$ is the "diagonal" subgroup $\Delta(G) = \{ (g,g) : g \in G \}.$ It is easy to check that the module is faithful if and only if $G$ has trivial center. Another theme related to the question is that of "models". For example, R. Richardson constructed monomial representations of the symmetric group which contain every irreducible complex representation just once. These are not quite permutation representations: one takes a certain sign character for the centralizer of each involution (up to conjugacy) of the symmetric group $S_{n}$, and induces that up to $S_{n}$. This can be done in such a way that the sum of these is multiplicity free, and contains every irreducible character. For the general linear group, there are also Gelfand-Graev representations.