First off, thank you for having the courage to post this. I'm sure other new divers reading it will avoid some mistakes because you wrote about yours.
There's so much inexperience playing a big role here. A more seasoned diver would have gotten suspicious at the 3500 psi fill in an Al80 -- Florida is notorious for overfilling tanks, but those are steel tanks in cave country, not aluminum tanks on the coast. In addition, a seasoned diver would have watched his gauge more closely, and discovered one of two things: Either the gauge wasn't moving, in which case it was broken and the dive needed to be ended, or the gauge WAS moving but was simply reading 500 psi high, which shouldn't have resulted in anyone being out of gas while still in the water (because the dive would have been ended with a plan to have at least 500 psi on surfacing, which in this case would have been out of gas, but not until arriving at the top). No matter what the mode of malfunction of the gas gauge was, it took some serious lack of attention to allow it to become an out of gas situation.
And that inattention goes along with the passivity at the beginning. Your GF simply wasn't an active participant in the dive. She let you set up her gear, and she came close to trying to get you to dive for her. She had no working depth gauge and a malfunctioning gas gauge, and was following you from behind -- WAY too passive. I would highly suggest that you never set her gear up for her again, and further, that you make her lead some dives and take more responsibility about her diving.
DD had a good point about positioning in current, too. This is another place where inexperience causes a problem -- if you aren't thinking about the "what ifs", you won't realize that ten feet of separation along a current line can be worse than 50 feet of separation in still water. In this case, you were lucky; the diver behind was the one who ran out of gas. What if it had been you?
Finally, the article already cited from NW Grateful Diver has one of the big clues to what went down here. An aluminum 80 at fill pressure holds 77 cubic feet of gas. If your SAC rate while swimming fast and looking for lobsters is 1 cf/min (not unreasonable -- .75 cfm is an "average" gas consumption rate for an adult male, and adding inexperience and exertion to the equation would make 1 cfm perhaps an overly conservative estimate) and you are at 3 ATA (66 feet), you'll use 3 cfm . . . which means you are going to drain the entire tank in about 26 minutes. If you want to reach the surface with 500 psi, you have only 65 cubic feet to use -- you're looking at no more than a 20 minute dive, assuming all goes well, and even then, you wouldn't have enough gas to get you and your GF to the surface at the end of 20 minutes, if she ran out of gas then.
I think a lot of new divers think 60 feet just doesn't sound that deep -- and it's not. But gas consumption really begins to build as you add the ATAs, and aluminum 80s are very small tanks, really, especially for novice divers whose gas consumption is always high. Add lobstering and towing a float, and you really should have expected to run out of gas in a very short time -- but of course, nobody gave you the tools to figure this out, so you had to learn it by a bad experience that both of you luckily survived unhurt.
Lessons learned . . . as a new diver, put the hunting aside for a while, until your diving skills and experience are more solid, and you have a good sense for how long a dive you can do. Both of you should take responsiblity for your gear, your plan, and your dive. Neither of you has enough experience to dive with any kind of equipment failure yet -- and as a general rule, it's unwise to dive with any significant equipment malfunction anyway. And both divers should have working dpeth and timing devices -- what if you got separated in the current? How is the person who doesn't know his depth going to control his ascent rate? (And yes, there are ways, and in the "good old days" people dove with no gauges at all. But we don't have to do that today, and we shouldn't.)
Keep diving -- you have wonderful reef diving where you are. But you might consider looking into a bigger gas supply, because a lot of that diving is deep enough that the single aluminum 80 is not a very good choice of tank. Again, read Bob's article, and do some calculations to see what happens to an Al80 at or below 60 feet -- it's not a pretty realization!