A number of weeks ago I was thinking of finding an example of a complete countable theory with only one binary predicate that is not $ω$-categorical. I later realized that $Th(\mathbb{Z},<)$ works, but an earlier thought was to find two non-isomorphic well-orders that have the same first-order theory. This sparked the question of what are all such pairs, and what is the smallest such pair.
I think $(ω^ω,ω^ω+ω^ω)$ is the smallest such pair (since $ω^k$ all don't work for finite $k$, by the winning strategy of David C. Ullrich in the comments below), but how to prove it? Is there a generalized criterion for determining when $Th(α,<) = Th(β,<)$ given two arbitrary ordinals $α,β$?
The following is true for all $\alpha, \beta >0$: $$Th(\omega^{\omega}\cdot \alpha,<)=Th(\omega^{\omega}\cdot \beta,<)$$ This and many related things including your conjecture can be proved using Erhenfeucht-Fraisse games. See Rosenstein: Linear Orderings.