Boundary between decidability and undecidability for small theories
Let $V_k (n)$ be the function that maps $n$ to the largest power of $k$ dividing $n$.  (Not the exponent of the largest power; the largest power itself.)  It follows from the work of Büchi (as corrected by, e.g., Hodgson) that the first-order theory Th($N, +, V_k$) for fixed integer $k \geq 2$ is decidable.  But Villemaire showed (￼Theoretical Computer Science 106 (1992), 337-349) that Th($N, +, V_k, V_l$) is undecidable if $k, l$ are multiplicatively independent.  So this is a nice boundary between decidable and undecidable.  

The survey paper of Bès (available here:  http://lacl.univ-paris12.fr/bes/publi/survey.ps ) makes good reading!