What is the way to convince myself that $\left\langle(1,2),\ (1,2,3,4)\right\rangle=S_4$ but $\left\langle(1,3),\ (1,2,3,4)\right\rangle\ne S_4$?
Let $\sigma$ be any transposition and $\tau$ be any $p-$cycle, where $p$ is a prime. Then show that $S_p=\langle\sigma,\tau\rangle$.
On
Not sure how to "convince" you, but I suspect you are worried because some of the 2-cycles do the job and others do not. The trick is in picking the right 4-cycle to go with your 2-cycle or vice versa. (1,2) works with (1,2,3,4) because 1 and 2 are adjacent in (1,2,3,4) whereas 1,3 is not. But (1,3) will work with (1,3,2,4).
For more info:
http://en.wikipedia.org/wiki/Symmetric_group#Generators_and_relations In particular it says the following is a generating set: "a set containing any n-cycle and a 2-cycle of adjacent elements in the n-cycle."
Besides to @Betty's points, there is another way for seeing why this happens. We know that $S_4$ can have the following presentation:
$$S_4=\langle a,b\mid a^2=b^4=(ab)^3=1\rangle$$ Let's satisfy $a=(1,2),~~b=(1,2,3,4)$ in above relations. Indeed $a$ and $b$ can do that, but what will happen if we set $a=(1,3),~~b=(1,2,3,4)$? By this assumption, we see that $(ab)^3=(1,4)(2,3)$ and this happens because of the points @Betty indicated them in detailed. Now if you are familiar to one of $D_8$'s presentation, then you'll have $$D_8=\langle a,b\mid a^2=b^4=(ab)^2=1\rangle,~~a=(1,3),~~b=(1,2,3,4)$$ instead which is of order $8$.