Elementary equivalence of ordinals

The first-order theory of well-orderings was studied in great detail in a paper of Doner, Mostowski, and Tarski, "The elementary theory of well-ordering -- a metamathematical study" [Logic Colloquium '77, edited by A. Macintyre, L. Pacholski, and J. Paris, North-Holland (1978) pp. 1-54]. In particular, their Corollary 44 characterizes (unless their notation is very non-standard --- I haven't checked carefully) when two ordinals are elementarily equivalent. Modulo an apparent typo in the definition just before the corollary (one of the strict inequalities should be non-strict), it seems that the first pair of distinct but elementarily equivalent ordinals is $\omega^\omega$ and $\omega^\omega\cdot2$. A thorough reading of the paper (which I don't have time for right now) should also reveal the answer to your second question, about elementary submodels (probably the same pair of ordinals).