I'm wondering if I can do this on NetBSD.  Is 850 MB enough for the
  NetBSD full install, plus lynx, links(graphical), icewm, mutt, popa3d;
  plus enough space to be able to keep the box up-to-date by applying
  security patches and building as necessary?  Its this latter part that
  I'm unsure of since I've never done it before to know how much space it
  takes.

For the base system, you can cross-compile it from another machine, and
it doesn't need to be the same OS or processor arch - amd64 with ubuntu
should be fine.  Then you can do a binary update.  See
pkgsrc/sysutils/etcmanage for the scripts I use.

The tough part will be building packages in that space.  Can you
nfs-mount space for /usr/pkgsrc?  If so, I think you can get this to
work.