I did some digging and it turns out I had autopushd set. No wonder I didn't understand the usefulness of pushd/popd; I was already using them.

Also, by "cd -" I meant cd -[tab], cd -1, cd -2, etc.

cd is a shell built-in, not an external command. It has to be, since it changes the directory of the shell process, which can't be done by a child process. So shells do have to implement this specially.