I just got back to my homebase Oahu after diving with Bubbles Below on Kauai.
I have also heard good things about Fathom Five from my instructor who gave me the Bubbles Below recommendation.
You might want to try a couple of operators.
I found the Bubbles Below staff to be excellent.
They were well organized and very knowledgeable. We had excellent ratios: two instructors and a divemaster for 6 divers on the boat and all of the staff were sea captains. They combined a lot of leisure paced education into the day, explaining a lot about Kauai, Hawaiian culture and such relating to the area we were going, and aquatic live particular to the area. Much more than a dive briefing usually entails.
The crew were very upbeat and very pleasant AT ALL TIMES with EVERYONE!
They passed out fresh sliced fruit, bagels with cream cheese, and later we had warm pizza! Pretty extravagant for a dive outing. In Oahu you might get a few cookies if you are lucky (and remembered to bring them from your own cupboard)! haha
We had a great trip to Mana Crack. The diving was good. The staff led us well, poiting out nudibranchs and other critters and making notes on their slates. They would give you lots of space too if you wanted it...to explore without TYPE A governance.
Regards a few of your other questions:
there is a weight limit of 50 lbs which may be strictly enforced of some carriers (the fine folks at Hawaiian let us through with 52)...
There is nitrox available. A few people on our outing had nitrox tanks.
Tec Diving...I have no knowledge at this point.
Regards Kauai diving in particular: if you are confident in you skills you might consider doing the Ni'ihau trip. Currents are a concern in Hawaii in general but if you have Tec experience you probably are well trained and adept at handling challenges. Visability, or rather turbidity, usually poses no problem. There are lots of things that can injure you here, but they are easy to avoid, look before you touch...or just don't touch. The most common injury I see is pricks from sea urchins (or Vauna (spelling??) as they are named here; they can easily be 8-10 inches across). One thing you will like is it is as warm as a bathtub here! Should be 79-80 degrees F.
Have fun!
Jason