The correct condition is that $m$ and $n$ are coprime, that is, have no common factors. In particular, this means that $C_2 \times C_3 \cong C_6$. (Sometimes it is hard to compare two multiplication tables by inspection, though it can help identifying two isomorphic groups from their tables by reordering the elements.)
Hint Given two groups $G, H$ and elements $a \in G, b \in H$, the order of element $(a, b)$ is the smallest number, $\text{lcm}(k, l)$ divisible by both the order of $l$ of $a$ and the order $k$ of $b$.
In particular, suppose $G$ and $H$ are cyclic, say $G = C_n$, $H = C_m$. Then, if $a$ and $b$ are generators of $C_n$, $C_m$, respectively, by definition they have respective orders $n, m$ and hence $(a, b) \in C_n \times C_m$ has order $\text{lcm}(m, n)$.
So, if $m, n$ are coprime, this order is $\text{lcm}(m, n) = mn$.
Conversely, if $m, n$ are not coprime, then since any $a \in C_n$ has order $l$ dividing $n$ and any $b \in C_m$ has order $k$ dividing $m$, we have that the generic element $(a, b) \in C_n \times C_m$ has order $\text{lcm}(k, l) \leq \text{lcm}(m, n) < mn$. In particular, no element has order $mn$, so $C_m \times C_n$ is not cyclic.
For example, the elements $1 \in C_2$ and $1 \in C_3$ generate their respective groups, and the powers of $(1, 1) \in C_2 \times C_3$ are
$$(1, 1), (0, 2), (1, 0), (0, 1), (1, 2), (0, 0),$$
so $(1, 1)$ generates all of $C_2 \times C_3$, which is hence isomorphic to $C_6$.
The two choices for the lower right quadrant do not amount to the same thing. The first choice results in the non-cyclic group which you call $Z_2 \otimes Z_2$ (I would call it $C_2 \times C_2$). The second one results in a cyclic group ($Z_4$, or $C_4$). You can match it with your $Z_4$ table by relabeling $A$ and $B$. (As Arthur pointed out in the comments, you did a similar relabeling earlier when you said "your $C$ is my $B$".) You can tell that these groups are really different because the first has the property that every element squares to $I$, and the second doesn't.
As for the second half of your question, let me first point out that it's not actually true that if $A^4 = I$, then the group is cyclic. In fact, even in the non-cyclic group, you also have $A^4 = I$; it's just that $A^2 = I$ too. What you mean to say is that if $A$ has order 4, then the group is cyclic. (In case you haven't seen this term yet, the order of $A$ is defined as the smallest $n > 0$ with the property that $A^n = I$.)
Now let me try to clarify how to do the classification in terms of cyclic subgroups. As you said, Lagrange's theorem implies that every element has order 1, 2, or 4. (And of course only the identity, $I$, has order 1.) If there is any element with order 4, then that makes the group cyclic. (It could be $A$, $B$, or $C$--and in fact it will be two out of those three--but as before you can rename elements so that $A$ is one of them.) If there is no element with order 4, then everything but $I$ must have order 2. This means that you have all $I$'s along the diagonal of your multiplication table. Given this, you can fill in the rest of the table using the "once and only once rule" that you mentioned. This proves that every group of order 4 is either $C_4$ or $C_2 \times C_2$.
Best Answer
The cyclic group of order 4 is the abelian group $\{1,a,a^2,a^3\}$, and the other group is $\{1,i,i^2,i^3\}$ so the isomorphism is quite easy to see. In your question you've put $-1$ as the second element, which is probably what confused you.