Constructions of the smallest nonabelian group of odd order

If $F$ is any field, there is a subgroup of $\text{PGL}_2(F)$ given by fractional linear transformation of the form $z \mapsto az + b$ where $a \in F^{\times}, b \in F$. This is precisely the subgroup fixing the point at infinity in $\mathbb{P}^1(F)$. Taking $F$ to be a finite field $\mathbb{F}_q$ we obtain a family of (usually) nonabelian Frobenius groups of order $q(q - 1)$.

Now, we can further restrict $a$ to lie in any subgroup of $F^{\times}$; in particular, for $q$ odd, taking it to lie in the subgroup of quadratic residues gives a family of (usually) nonabelian groups of order $\frac{q(q-1)}{2}$. Taking $q = 7$ gives the desired group.

Well, without Sylow theorems and semidirect products not many options remain open... and thus constructing such a group will look a little (or a lot) like out of the blue.

Anyway, the non-abelian group of order $\,21\,$ can be given as

$$G=\langle\,x,y\;\;;\;\;x^3=y^7=1\;,\;xy=y^2x\,\rangle\cong\langle\,(235)(476)\;,\;(1234567)\,\rangle\leq S_7$$

It is, I suppose, easier to show that the right hand group, with permutations, gives us what we want, but none is as easy as expressing the group as a semidirect product.

How about a mix of DonAntonio's two answers? He writes:

Anyway, the non-abelian group of order 21 can be given as $G=\langle\,x,y\;\;;\;\;x^3=y^7=1\;,\;xy=y^2x\,\rangle\cong\langle\,(235)(476)\;,\;(1234567)\,\rangle\leq S_7$

Give both the presentation with generators and relations, and its realization with x and y in $S_7$. It's easier to calculate with the former, and clear that the group has no more than the 21 elements $x^i y^j$ for $0 \leq i \leq 2$ and $0 \leq j \leq 6$. But it's not clear that the presentation doesn't "collapse" by having the given relations produce additional relations that identify some of these 21 elements. On the other hand, it's easy to show that the two permutations satisfy the relations, and the group they generate must have at least 21 elements by Lagrange's Theorem.

The group is the 'odd subgroup' in $GL_3(2)$.

OP specified the students haven't done finite fields, but if they've done regular matrices, then "vectors of bits" and "matrices of bits" may seem quite natural and certainly does not require explanation of finite fields in general.

The group clearly has 168 elements. If they've done Lagrange perhaps they might suspect there's a subgroup of order 21.

$$ x=\begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}, y=\begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix} $$ $x$ manifestly has order 3, and conjugating by $x$ just rotates the rows and columns of a matrix (this is true in any field). $y$ is not so manifest, but you can start from any non-zero vector and write out its images under repeated action of $y$, to show that it cycles through all seven non-zero vectors. This also lets you read off $y^2$. Hooray, $x^3 = 1, y^7 = 1, y^2 = y^x$.