This is a question which arose while working through Flajolet-Sedgewick's Analytic Combinatorics.
In their terminology, the cartesian product of two combinatorial classes $\mathcal{A},\mathcal{B}$ gives a new combinatorial class
$$\mathcal{C}=\mathcal{A}\times \mathcal{B}$$
and the generating function of $\mathcal{C}$ is simply
$$C(z)=A(z)\cdot B(z).$$
However, this rule assumes that the "size" of the objects in $\mathcal{C}$ is inherited as
$$\forall a\in\mathcal{A},b\in\mathcal{B}:|(a,b)|_{\mathcal{C}}:=|a|_{\mathcal{A}}+|b|_{\mathcal{B}}$$
Now, assume I define a different product $$\mathcal{C}=\mathcal{A}\circ\mathcal{B}$$ which shall fulfill that
$$|(a,b)|_{\mathcal{C}}:=\max(|a|_{\mathcal{A}},|b|_{\mathcal{B}})$$
What would then be the rule to obtain $C(z)$. Simple counting brings me to
$$C(z)=\sum_{n,m\in\mathbb{N}_0}A_n B_m z^{\max(n,m)}=...$$ $$ = \sum_{k\in\mathbb{N}_0}\left(\sum_{n\leq k}(A_n B_k+A_k B_n)-A_k B_k\right)z^k$$
But I was unable to bring this to a "simple" form, which expresses $C(z)$ in terms of $A(z)$ and $B(z)$. Can anyone help?
Note that if $\sum_kA_kz^k=A(z)$, then
$$ \left(\sum_{n\le k}A_n\right)z^k=A(z)(1+z+z^2+\cdots)=\frac{A(z)}{1-z}\;. $$
Thus you have
$$ \sum_{k\in\mathbb{N}_0}\left(\sum_{n\leq k}(A_n B_k+A_k B_n)-A_k B_k\right)z^k=\frac{A(z)}{1-z}\star B(z)+A(z)\star \frac{B(z)}{1-z}-A(z)\star B(z)\;, $$
where $\star$ denotes the Hadamard product given by coefficient-wise multiplication. As discussed e.g. here, here and here, Hadamard products are non-trivial. Since the equation can't be solved for a Hadamard product, it doesn't prove that your problem is equivalent to (and hence as hard as) taking Hadamard products, but it does show that if you do find a simpler form, it's going to have to involve at least a bit of a detour. My guess would be that this is the best you'll be able to get in the general case.