I think this fails at the "preferably simple" stipulation...

It is a theorem of Wise that for each finitely presented group $Q$ there is a finitely generated residually finite group $N$ such that $Q\leq \operatorname{Out}(N)$. So, in some ways, every finitely presented group occurs in nature...(See "A residually finite version of Rips's construction", Corollary 3.3).

Also, if $G$ is finitely related your finite-index subgroup will be finitely related also.

I know you said you do not want examples, but the primitive pairs in $F(a, b)$ where $a$ and $b$ only occur with positive exponent work', as can be seen from your algorithm (i.e. if $<u, v> = F(a, b)$ and $u, v \in S_i$ for some $i$ then your word works). Thus, for example, $W=uvu$ works. The primitive pairs work because your algorithm can be used to unpick' the automorphisms $a\mapsto ab, b\mapsto b$, $a\mapsto ba, b\mapsto b$, and $a\mapsto b, b\mapsto a$ of $F(a, b)$. Also, I am unsure how one would gain a complete description; if $W$ works then so does, for example, $W^iUW^j$ for all $U$

@ Mark: I am a bit confused by how the algorithm begins; in each step you take two words from $S_n$, but $S_0$ contains only one word.

Is the Largeness order not a dcpo (search for `the concept of largeness in group theory'; bascially $H\leq G$ if there exists a finite-index subgroup of G which maps onto a finite-index subgroup of H, and the kernel is finite)? Here free groups (and groups with a finite index subgroup which map onto free groups) sit at the top, while the trivial group lies at the bottom.

It is an epsilon off topic, but, `All mathematics is built up by combinations of a certain number of primitive ideas, and all its propositions can, but for the length of the resulting formulae, be explicitly stated in terms of these primitive ideas; hence all definitions are theoretically superfluous.' -Bertram Russell, Principles of Mathematics, Chapter XILX

I quite like the fact that one can apply a sequence of arbitrary moves (aka an arbitrary group element) a finite number of times to get back to where you started from (because, of course, every element in your group has finite order). This is quite easy to demonstrate (given finite time...) It is also trivial (but interesting!) to note that there is no single sequence of moves (aka group element) which will take any position and return it to the `solved' cube. This is basically asking if your group is cyclic, and it obviously isn't.

This problem - the Fifteen puzzle - is one of my all-time favourites. It has an interesting history too, en.wikipedia.org/wiki/Fifteen_puzzle