Hi SailNaked,
I recently went through the same process.
I was certified in 1978 with NAUI and the instructor was great, he became a mentor and friend. I stayed with NAUI for a "Sport Diver" class (OWII or Advanced), Rescue, Assistant Instructor and finally did my ITC in 1985. I stayed with NAUI because I found the way they did (do) things matched my personality and attitude towards diving.
In the late 80's and early 90's I was diving wrecks and walls that would now be considered tech dives - we did have doubles and deco O2, but no helium and no specific training - just mentoring and stealing from the Florida cave diving community.
Fast forward to this past August. I wanted to update myself given the technology and training that was now available for tech diving. I wanted to stay with NAUI, but here on the wet coast of Canada, NAUI has completely disappeared... as far as I can tell. I could not find a NAUI tech instructor. So, I talked with an exploratory tech diver buddy and he suggested that the agency mattered less than a good instructor. So, I've just finished the first couple of courses with a DSAT instructor. He is a good instructor - always available if I have questions, concerns or issues and has what I think is a balanced approach. I think his courses and teaching style is a good fit for me. I have to admit, though, I'd be lying if I told you I'm only somewhat curious about how different a NAUI course/instructor would have been...
So, I'd suggest you talk to a prospective instructor and interview them - as much as they should want to interview you as a prospective student. The other points to consider are the methodologies of the agency - helium now or later, ratio deco or computers, for example.
Like most have already said, take the time to find a good instructor and enjoy the class. Oh, be prepared to learn to dive all over again!
Hope that helps.
Lee