[EDIT: I rewrote the first couple of paragraphs, because I realized a better way to say what I had in mind.]
There are many ways to define dimension and some of them give the same answer some of them don't.
Depth is a sort of dimension. Perhaps not the most obvious, but one that works well in many situation.
In general we count dimension by chains and the main difference between Krull dimension and depth is about the same as the difference between Weil divisors and Cartier divisors.
For simplicity assume that we are talking about finite dimensional spaces. Infinite dimension can be dealt with by saying that it contains arbitrary dimensional finite dimensional spaces where we may substitute "Krull dimension" or "depth" in place of "dimension".
I usually think of Krull dimension as going from small to large: We start with a (closed) point, embed it into a curve, then to a surface until we get to the maximal dimension. However, for comparing to depth it is probably better to think of it as going from large to small: Take a(n irreducible) Weil divisor, then a(n irreducible) Weil divisor in that and so on until you get to a point.
In contrast, when we deal with depth we take Cartier divisors: We start with the space itself (or an irreducible component), then take a(n irreducible) hypersurface, then the intersection of two hypersurfaces (such that it is a "true" hypersurface in each irreducible component this condition corresponds to the "non-zero divisor" provision)=a codimension $2$ complete intersection, and so on until we reach a zero dimensional set.
So, I would say that the geometric meaning of Cohen-Macaulay is that it is a space where our intuition about these two notions giving the same number is correct. I would also point out that this does not mean that necessarily all Weil divisors are Cartier, just that one cannot get a longer sequence of subsequent Weil divisors than Cartier divisors.
Another, less philosophical explanation is the following:
Cohen-Macaulay means that depth = dimension. $S_n$ means that this is true up to codimension $n$. Then one may try to give geometric meaning to the $S_n$ property and say that CM means that all of those properties hold.
So,
$S_1$ --- means the existence of non-zero divisors, i.e., that there exists hypersurfaces that are like the ones we imagine.
$S_2$ --- is perhaps the most interesting one, or the one that is the easiest to explain. See this answer to another question where it is explained how it corresponds to the Hartogs property, that is, to the condition that functions defined outside a codimension $2$ set can be extended to the entire space.
$S_3$ --- I don't have a similarly nice description of this, but I am sure something could be made up, or some people might even know something nice. One thing is sure. This means that every ("true") hypersurface has the $S_2$ property, which has a geometric meaning as above.
[...]
So, one could say that
$S_n$ means that every ("true") hypersurface has the $S_{n-1}$ property, which we already described.
I realize that this description of $S_n$ may not seem satisfactory, but in practice, this is very useful. I would also add that in moduli theory it is actually important to know that some properties are inherited by hypersurfaces (=fibers of morphisms), so saying that hypersurfaces are $S_2$ is actually a good property.
More specifically, for example, the total space of a family of stable (resp. normal, $S_2$) varieties is $S_3$ ("is" as in "has to be"). Then one might (as in Shafarevich's conjecture, see Parshin's Theorem, Arakelov's Theorem, Manin's Theorem, Faltings' Theorem) study deformations of these families (say the embedded deformations of a curve in the moduli stack of the corresponding moduli problem). Then the total space of these deformations ought to be $S_4$ on account of their fibers having to be $S_3$ since their fibers have to be $S_2$. This actually explains why it is not entirely bogus to say that $S_4$ means that codimension $2$ complete intersections satisfy the Hartogs property.
This actually reminds me another thing that is important about CM. A lot of properties are inherited by general hypersurfaces. The CM property is inherited by all of them. This makes them perfect for inductive proofs.
One way to see that a surface is CM is that normal $\Rightarrow$ CM. Of course, the point is that normal is equivalent to $R_1$ and $S_2$, so it always implies $S_2$ and if the dimension is at most $2$, then $S_2$ is the same as CM. If you have a non-normal surface, but it is non-normal only because it has normal crossings in codimension one, then it is CM. You may also try to test directly for the Hartogs property mentioned above:
A reduced surface $S$ is Cohen-Macaulay if and only if for any $P\in S$ and any regular function $f$ defined on $U\setminus \{P\}$ for an open set $P\in U\subseteq S$ there exists a regular function $g$ on $U$ such that $g_{|U\setminus \{P\}}=f$.
1
You are right. The Auslander-Buchsbaum-Serre theorem implies that the projective dimension of a CM module over a regular local ring is $0$ and hence a CM sheaf over a regular scheme is locally free.
2
It is quite easy to give examples of non-locally free CM sheaves.
(a)
It is relatively easy to prove that if $X$ is CM, then $\omega_X$ is a CM sheaf.
So, take any $X$ that is CM, but not Gorenstein. Then $\omega_X$ will be a non-locally free CM sheaf. Here is an explicit example:
$$X=\mathbb A^3/(x,y,z)\sim (-x,-y,-z)$$
See this MO answer for a proof that $\omega_X$ is not locally free. The fact that this $X$ is CM follows from that it is a finite quotient.
(b)
Let $X$ be a normal surface (hence it is CM) and $\mathscr F$ an arbitrary reflexive sheaf of rank $1$. Reflexive sheaves are $S_2$ and hence on a surface CM, but they're not always locally free. In fact, these sheaves correspond to Weil divisors while locally free sheaves of rank $1$ correspond to Cartier divisors.
So for these sheaves there is a criterion you are looking for:
A reflexive sheaf of rank $1$ (which is CM on a normal surface) is locally free if and only if the associated Weil divisor is Cartier.
3
I don't know if there is an elegant criterion for a CM sheaf to be locally free. There is one result that is sometimes useful:
Let $f:X\to Y$ be a morphism with equidimensional fibers. If $Y$ is regular and $X$ is CM, then $f$ is flat.
In particular, if $f$ is finite, then $f_*\mathscr O_X$ is locally free.
Best Answer
I will argue that the examples you gave are "simplest" in some strong sense, so although they look unnatural, if Martians study commutative algebra they will have to come up with them at some point.
Let's look at the first one $A=k[[x,y,z]]/(x^2-y^2, y^2-z^2, xy,yz,zx)$. Suppose you want
Then it would look like $A=R/I$, where $R$ is regular and $I$ is of height equals to $\dim R$. If $\dim R=1$ or $2$, then $I$ would have to be a complete intersection, no good (now, the poor Martian may not know this at the begining, but after trying for so long she will have to give up and move on to higher dimension, or prove that result for herself). Thus $\dim R=3$ at least, and we may assume $R=k[[x,y,z]]$ (let's suppose everything are complete and contains a fied).
Since $I$ is not a complete intersection, it must have more than $3$ minimal generators. If it has $4$ then it would be an almost complete intersection, and by an amazing result by Kunz (see this answer), those are never Gorenstein.
So, in summary, a simplest $0$-dimensional Gorenstein but not complete intersection would have to be $k[[x,y,z]]/I$, where $I$ is generated by at least $5$ generators. At this point our Martian would just play with the simplest non-degenerate generators: quadrics, and got lucky!
(You can look at this from other point of view, Macaulay inverse system or Pfaffians of alternating matrices, see Bruns-Herzog, but because of the above reasons all the simplest examples would be more or less the same, up to some linear change of variables)
On to your second example, $k[[t^3,t^5,t^7]]$. Now very reasonably, our Martian wants
Since $\dim B=1$, being a domain would automatically make it Cohen-Macaulay. The most natural way to make one dimensional domains is to use monomial curves, so $B=k[[t^{a_1},...,t^{a_n}]]$. But if $n=2$ or $n=3$ and $a_1=2$ you will run into complete intersections, so $a_1$ would have to be $3$ and $n=3$ at least, and on our Martian goes...
(Again, you can arrive at this example by looking at things like non-symmetric numerical semi-groups, but again you would end up at the same simplest thing).
Reference: I would recommend this survey for a nice reading on Gorenstein rings.