I don't like running out of air in a sub. I think an entire revamp of the sub dynamics would do nicely.                                                                                         

I propose that subs should have unlimited underwater time, but go very slow while submerged. Currently I have a barracuda that can go 22 submerged, 34 OH. I find that rediculous.

Instead of subs going unrealisticly fast under water, slow them down to realistic speeds. The real barracuda went 9 knots underwater. In-game submarines should go a similar speed, with at max a 20 knot OH.

This will change the way people play subs. They will lumber over to the other side, and have to wait for the right moment to strike. Enemy ships will have to come to them. If the sub's team is winning, there is a chance that sub won't see any action at all because of slow speeds.
These changes might affect the differences between tier classes, because if all subs travel at a similar speed, there won't be much difference between SS1 and SS5. More support slots and DP should be a sufficient enough difference however.

BB drivers might complain that they never see the enemy subs, and thus get sunk by them unfairly. Is it unfair? That is up to the community to decide. DDs and FFs will be as dangerous as ever, and HHs and DCs will always be leathal.

To summarize:
Give submarines unlimited underwater time
Slow subs down to something around 10 knts (20knts max OH) under water