[Edited due to YCor's comment:]
Given a finite group $G$, under what conditions does $G\times G\times G$ (the direct product of three copies of $G$) admit a faithful group action on a set of size $|G|$? This is equivalent to an injective group homomorphism from $G\times G\times G$ to $S_{|G|}$.
For reference, for every group $G$ with a trivial center, $G\times G$ admits an easy faithful group action on $G$ by $(g_1, g_2): g \rightarrow g_1 g g_2^{-1}$.
Best Answer
I think it is possible to give a fairly precise description of the groups $G$ which fail to satisfy the condition given by @YCor in comments, with the exception of the case that $G$ is a $2$-groups. I will say a few words later about the case that $G$ is a $2$-group, and I think understanding the exceptional $2$-groups is not completely intractable with some more work. Of course, this also makes use of the comments of @AchimKrause above.
So now let $G$ be a finite group which has no faithful permutation action on a set of cardinality $\frac{|G|}{3}$ or less, and suppose further that $G$ is not a $2$-group.
As I noted in comments, every subgroup of $G$ of any odd prime order is normal, for otherwise $G$ has a faithful permutation action on $\frac{|G|}{p}$ points for some odd prime $p$. Furthermore, if $p$ is any prime greater than $5$, then $G$ has cyclic Sylow $p$-subgroups. For otherwise, $G$ has an elementary Abelian subgroup of order $p^{2}$, and $G$ contains distinct subgroups $Q$ and $P$ of order $p$, in which case $G$ has a faithful permutation action on $\frac{2|G|}{p}$ points.
Now we note that if $p_{1}, p_{2}, \ldots ,p_{k}$ are all the odd prime divisors of $|G|$, then $G$ has a (normal) subgroup, say $K$, of order $\prod_{i=1}^{k} p_{i}.$
Suppose then that $4$ divides $|G|.$ Let $S$ be a Sylow $2$ subgroup of $G$. Then $G$ has a faithful permutation action on $[G:K] + [G:S]$ points, so that $|K| \leq 12$, and we also see that $|S| < 8$ if $|K| > 3$.
We conclude that if $4$ divides $|G|$, then $|G|$ has only two prime divisors, since $|K| \in \{3,5,7,9,11 \}$. Hence $G$ is solvable (by Burnside's $p^{a}q^{b})$-theorem, which is probably overkill here, but saves time), since $|K|$ is divisible by every odd prime divisor of $|G|$. Let $R$ be a Sylow $p$-subgroup of $G$ for the unique odd prime divisor of $|G|$. Then $[G:S] + [G:R] > \frac{|G|}{3}$ so that $|R| \leq 11$.
Hence in the case that $4$ divides $|G|$ (and $G$ not a $2$-group), we have $|G| \in \{20,28,36,44 \},$ or else $G$ has order $3 \times 2^{k}$ with $k \geq 2$.
Thus we may suppose that $4$ does not divide $|G|$. Suppose first that $G$ has even order. Then since $G$ has a cyclic Sylow $2$-subgroup or order $2$, $G$ has a normal $2$-complement, that is, (in this case), a normal subgroup, say $H$, of index $2$. There can be at most one odd prime $p$ such that $G$ has a Sylow $p$-subgroup of order $7$ or more ( later note added for clarity: otherwise if $P$ and $Q$ are Sylow subgroups for distinct odd primes, then $G$ has a faithful permutation representation of degree $[G:P] + [G:Q] \leq \frac{|G|}{3}$.).
Furthermore, from the discussions above, we know that if $|H|$ has two different odd prime divisors $p$ and $q$, then $G$ now has subgroups of order $2p$ and $2q$. In that case, if the Sylow $2$-subgroup of $G$ is not normal, then we obtain a faithful permutation representation of degree $\frac{|G|}{2p} + \frac{|G|}{2q} \leq \frac{|G|}{3}.$ (Later note added for clarity: so, we have established that if $G$ is not isomorphic to a direct product $C_{2} \times H$, then $G$ is a isomorphic to a semidirect product of $H$ with $C_{2}$, with non-trivial action of $C_{2}$ on $H$, and that $H$ is a $p$-group for some odd prime $p$ in that case).
Hence we conclude that either $H$ is a $p$-group for some odd prime $p$, or that $G = S \times H$ where $|S| = 2$ and $|H|$ has at least two prime divisors. Let $p$ and $q$ be prime divisors of $|H|$. If $p \geq 7$, then we obtain a contradiction, since $G$ has a subgroup of order $2q \geq 6$ and a subgroup of order $p$.
Hence we now are left with the so far untreated cases $|H| \in \{ 45,75,15 \}.$ If $|H| = 45,$ then $G$ has subgroups of order $18$ and $5$, leading to a contradiction. If $|H| = 75,$ then $G$ has subgroups of order $6$ and $25$, leading to a contradiction.
Now we are left with the case $|H| = 15$, and $G$ cyclic of order $30$.
Hence we are now left with the case that $G$ has odd order. We could quote the Feit-Thompson odd order theorem which seems like overkill, but we can avoid that here.
Suppose that $G$ is not a $p$-group for any prime $p$. If $|G|$ has three or more prime divisors, then the hypotheses on $G$ force the prime divisors of $|G|$ to be $3$, $5$ and $7$. (Later edit: Better argument- since we know that $G$ has subgroups of order $7$ and $15$, we have a contradiction- recall that we know that every subgroup of prime order is normal).
Hence we may suppose that $|G| = p^{a}q^{b}$ for distinct odd primes $p,q$. We have seen earlier that either $p^{a} \leq 5$ or $q^{b} \leq 5.$ If $p^{a} = 5$, then we obtain $q^{b} \in \{3,7 \}.$ If $p^{a} = 3$, then we can place no further restriction on $q^{b}.$
Later edit: Sean Eberhard's comment came in while I was writing this.
Later edit due to questions in comments: We are left with the following possibilities :
a) $G$ has odd order, and $|G| \in \{p^{k}, 3q^{k}, 35 \}$ where $p,q$ are odd primes and $q > 3.$ Furthermore $G$ is a direct product of a group of order $3$ with a cyclic $q$-group in the case that $3$ divides $|G|$ and $G$ is not a $3$-group.
b) $|G| = 2m$ for some odd integer $m$, and $G$ has a normal Sylow $2$-subgroup. Either $G$ is isomorphic to a direct product of a group of order $2$ with a $p$-group, where $p$ is an odd prime, or else $G$ is cyclic of order $30$.( Edit: in fact, $G$ cyclic of order $30$ is not exceptional- in that case, $G$ has three subgroups with trivial intersection, of order $6,10,15$, giving a faithful permutation representation of degree $5 + 3 + 2 = 10$).
c) $|G| = 2p^{k}$ for some odd prime, and $G$ is isomorphic to the semidirect product of a group of order $p^{k}$ with a group of automorphisms of order $2$ acting non-trivially on it. In fact, one can see in this case that the Sylow $p$-subgroup of $G$ must be cyclic, since otherwise, there are two different (normal, as explained earlier) subgroups of order $p$, and then two different subgroups of order $2p \geq 6$, giving a faithful permutation representation of $G$ of degree $\frac{|G|}{2p} + \frac{|G|}{2p} = \frac{|G|}{p}$. Hence $G$ is a dihedral group in this case. Note that these are genuine exceptions, since if $G$ is dihedral of order $2p^{k}$ for $p$ an odd prime, then the only subgroup of $G$ which does not contain the unique (normal) subgroup of order $p$ of $G$ is a Sylow $2$-subgroup of $G$ of order $2$.
d) $|G| \in \{20,28, 36,44 \}.$ There are cyclic exceptions of each of these orders.
e) $|G| = 3 \times 2^{k}$ for some $k \geq 2$. There exceptional nilpotent subgroups of this type for every $k$ since if $G$ has cyclic or generalized quaternion Sylow $2$-subgroups, then every subgroup of $G$ of even order contains the unique involution of $G$.
f) $G$ is a $2$-group.
In all cases, for each odd prime $p$, every subgroup of $G$ of order $p$ is normal, and for each prime $ p > 5$ the Sylow $p$-subgroups of $G$ are cyclic (allowing the trivial group) .
In fact, following the discussion in comments below with Sean Eberhard, it is the case that the Sylow $p$-subgroups of $G$ are Abelian for all odd $p$, and Sean describes the possibilities for the odd Sylow $p$-subgroups in his answer about the Abelian case.