You may have answered your own question.Most adult males on an AL80 run low on air just before they run out of bottom time. "Bigger" divers and the "less experienced" burn it up sooner. Running out of air is easier for the divemasters to watch than running out of bottom time, so I don't blame the dive operations for erring on that side. Kids and small women can get away with 72s and smaller, but it is sloppiness on the dive boat's part to start a full grown guy's dive with anything less than 80 cu ft at 3000 psi. Such a shop deserves to get the maximum possible negative publicity for it. I own a pair of steel 120s personally; the extra weight is worth running out of bottom time instead of air. It would be nice if a dive boat would let folks specify a bigger tank and/or Nitrox mix for a set extra fee. As a capitalist, I accept the concept of extra bottom time = extra money. Anyone else know why they don't use that tactic for the extra revenue?
When I started diving the general rule, with US Navy tables, was that if you stayed above 100' you could not get yourself bent on a single steel 72 in a 12 hour dive day. I had very good SAC, so after playing with the tables I realized I had to adjust the depth upward to 90 feet for that to be entirely true.
With AL 80s (77 cu ft) and Nitrox it gets a little more complicated, but at shallower depths, even with current tables, the same is mostly true - but only for the first dive.
Assuming a 500 psi reserve, you have 64 useable cu ft in an AL 80.
With a SAC of .6, on air you would have:
38 minutes at 60 ft (50 minute NDL)
34 minutes at 70 ft (40 minute NDL)
31 minutes at 80 ft (1 minute over the 30 minute NDL)
And with 32% Nitrox, considering the equivalent air depth and rounding down on the same table, you get:
60ft - 70 minute NDL
70ft - 50 minute NDL
80 ft - 40 minute NDL
Placing all three dives well within the NDL on the first dive. However even with 32% nitrox after a 90 minute surface interval, you would have to stay above 60 ft to stay within the NDLs for the second dive with the gas you have available in an AL80.
Air is less forgiving on the second dive requiring much shallower depths in the 40 ft range on the second dive to stay within the NDL with an AL80.
So from a deco perspective, I can see why an operator may want to only supply smaller tanks if the depths are greater than 80 ft for the first dive or 60 ft for the second dive (and 60ft/40ft on air) - if they are operating with a boat load of pretty fish tourist divers who don't know enough to limit their bottom time.
If it were me having to deal with a boat load of unknown or inexperienced divers with dependents who have attorneys on retainer and the depths were in the 80'/60' range, I'd be tempted to provide AL80s with 32% or 36% to the nitrox certified divers and AL50s to the non nitrox certified divers.