In the past I have used Samba with Active Directory to allow network users to log into Linux machines. Today I'm maintaining a smaller network comprised only of Linux hosts, but I would still like to centralize authentication. I have looked into setting up a Samba host as a Domain Controller, but I don't exactly see the point of doing this when there are no Windows hosts. I've looked into NIS but it seems like it might be a bit complicated for my taste.
It is important that network-authenticated users share the same UIDs because there will be some shared disk resources involved as well.
For what it's worth the majority of my network nodes are OpenVZ containers, though there are some outliers (laptops, workstations, and a couple dedicated servers).
Have you looked into 389 Directory Server/RedHat Directory Server? We've used it on small clusters of Linux only machines with great success, it essentially provides LDAP/Active Directory-like services for a Linux domain.
Getting a base LDAP install ready isn't brain dead simple, but it isn't rocket science either and can be done in a few hours. I wouldn't use NIS for a new install, this is legacy technology.