I've had personal experience with steel 72s, AL80s, steel 100s and I have a buddy who used AL100s. Out of those cylinders, I'd recommend the HP steel 100s for boat dives or anything over 40fsw. I had never come even close to running out of gas...NDL chases me out first.
However, you might not want to rule out some slightly bigger tanks. I got a mild case of cylinder envy on a charter the other day. I thought I was manly lugging my steel 100s on the boat. That was until I helped the other four guys load their 108s, 120s, etc. on the boat. I felt a little inadequate.
Don't worry, I just e-mailed my counselor.
All kidding aside, there are other sizes of tanks out there -- both HP and LP tanks -- which I have no experience with but do see on boats quite often. Hopefully, someone who owns one of those tank sizes will chime in. No matter what size you buy, I would highly recommend a steel tank in general due to factors already mentioned. Good luck.
LobstaMan