There is a $(8,20,3)$ binary block code. Any linear code with minimal distance 3 and length 8 must contain fewer codewords. (We can see this from the Hamming bound.) Is 8 the smallest possible value of $n$ such that there exists a binary nonlinear $(n,M,d)$ code and for any linear $(n,K,d)$ code we have $K<M$?
If there were an even shorter example I might show it to my students as part of the brief discussion of coding theory in a course I am giving. I tried looking online, and discovered the $(8,20,3)$ example, but nothing that made it obvious whether this was the smallest possible example.