Assume that $(A,\leq)$ and $(B,\leq)$ are linearly ordered sets. Define a relation $R$ on $A\times B$ by $(a,b)R(c,d)$ iff $a<c$ or both $a=c$ and $b\leq d$. Prove that $R$ is a linear order on $A\times B$.
So basically we need to prove that elements of $A\times B$ are comparable. So that's how I do it, tell me if I am wrong.
Proof: Let $a,c \in A$ and $b,d \in B$ be such that $a=c$ and $b\leq d$. Then $(a,b)R(c,d)$. Then $(a,b)\leq (c,d)$ so it is comparable. Thus $R$ is linear order on $A\times B$.
Do I need to do the other case where $a<c$?
Your proof doesn't work because when you say
you are leaving out all of those choices of $a,c \in A$ and $b,d \in B$ where $a \neq c$ or $b \not\leq d$. And likely there are many of such choices. (For example, if $A = B = \mathbb{R}$ with the usual ordering, then the choice $a = 0$, $c = 10^{100}$, $b = \pi$, $d = -e$ is omitted.) So you only prove that $\langle a,b \rangle \mathrel{R} \langle c,d \rangle$ for a very specific collection of pairs of elements $\langle a,b \rangle , \langle c,d \rangle$ of $A \times B$.
Instead your proof should begin with arbitrary $a,c \in A$ and $b,d \in B$ (or, equivalently, with arbitrary $\langle a,b \rangle , \langle c,d \rangle \in A \times B$). Now we need to show that either $\langle a,b \rangle \mathrel{R} \langle c,d \rangle$ or $\langle c,d \rangle \mathrel{R} \langle a,b \rangle$. Of course, since $a,c \in A$ and we know that $A$ is linearly ordered by $\leq$, this tells us that one of three things hold: $a < c$ or $a = c$ or $c < a$. (I'll let you continue from here, looking at these three cases.)