Without any doubt, Gauss is considered one of the greatest mathematicians in history. However, digging into my mind, I don't remember any iconic theorem that was proved by him.
On the contrary, for example, Euler has a few famous results that everyone remembers: Formulas like $e^{i\pi}+1=0$ or $V-E+F=2$ or $\zeta(2)=\frac{\pi^2}{6}$, etc.
My question is that what are the greatest and most beautiful works of Gauss? Consider that you want to explain the majesty of Gauss to some fresh math student. What will you show him?
I recommend to you Chapter 10 from Barry Mazur and William Stein, Prime Numbers and the Riemann Hypothesis, Cambridge University Press (2016). Also you can find more about Gauss work on prime numbers from different references as companion of this nice book, I say Gauss law for the distribution of prime numbers.