Netscape Enterprise Server works great, and is easy to administer. It's not free like Apache, but Perl CGI works without any issues whatsoever on NT4 (both server and workstation).

My most recent client went with Netscape over apache for two simple reasons. They were comfortable with applying SSL certificates to it, and they could get a support contract from Netscape.

Personally, I would prefer apache.

Good luck!