The choice between NIS and NIS+ is easy - use NIS if you don't have to use NIS+ or have severe security needs. NIS+ is _much_ more problematic to administer (it's pretty easy to handle on the client side, but the server side is horrible). Another problem is that the support for NIS+ under Linux is still under developement - one major thing it still lacks is support for data encryption/authentication which is _the_ major thing why anyone would want to use NIS+...
The choice between Traditional NIS or the NIS code in the NYS library is a choice between laziness and maturity vs. flexibility and love of adventure.
The "traditional NIS" code is in the standard C library and has been around longer and sometimes suffers from it's age and slight inflexibility.
The NIS code in the NYS library, on the other hand requires you either to recompile and relink all your programs to the libnsl library, or recompile the libc library to include the libnsl code into the libc library (or maybe you can go get a precompiled version of libc from someone who has already done it).
Another difference is that the traditional NIS code has some support for NIS Netgroups, which the NYS code doesn't (yet). On the other hand the NYS code allows you to handle Shadow Passwords in a transparent way.