Well I am a big dummy.

My /etc/ssh/sshd_config was from my old install of 2.x and did not
include the "UsePam yes"  that is now default.  So that explains why I
couldn't get PAM going :(

But, I also think I know why s/key doesn't work when UsePam is set to
no or commented out. Starting with 4.0p1, openssh has this in
auth-chall.c:

get_challenge(Authctxt *authctxt)
{
/* ... */
#ifdef USE_PAM
        if (!options.use_pam)
                remove_kbdint_device("pam");
#endif
/* ... */
}

NetBSD-3.0BETA, using openssh-3.9, does not (I don't think -current
has this either).  So when I try to login, sshd will try pam, then
when that fails because UsePam is set to no, it will end there and not
attempt s/key.  I built openssh-4.2p1 with both pam and skey enabled,
UsePam set to no, and s/key works just fine.

I have filed this as bin/31517