I'd stick with pushd and popd every time, it's considerably more expressive.
is that an advantage? Do you have the time to explain this a bit more?
I feel that new users need less expressiveness, to avoid decision overload, and keeping one automatic directory save point is easier to mentally manage than a stack of them.
I do recommend using pushd/popd in shell scripts (always) and interactively (if you must), but I think 'cd -' should be the first thing you introduce to newcomers w.r.t tracking working directory changes.
That said, I don't disagree that cd - is a good introduction to the idea that there's more to the cd command than meets the eye. (I'm also a big fan of the CDPATH variable, despite its issues.)