Nice job. If the guy wasn't yelling out the seconds as you approached 16min, you should have choked him.
I was always fit, but ran low miles, maybe 30 miles a week. I broke 16 a few times, but they were probably mismarked. My 5K PR was only 16:20, and a few 34 minute 10K's. I did run my PR 10K after being out all night in Atlanta before Peachtree with USMC buddies; strange, but it's weird what you can do when you are in shape, I wish I had someone to help me take it seriously at the time. Flight school took up all my time. At 39 now, I train my ass off just to run 5:40 pace, but I all my PR's 15K and above are recent.
My claim to fame was 100% 300 PFTs from OCS through 7 years of active duty; probably about 25 career scored PFT's. I also got the TBS/Quantico course record for the "Endurance Run"; 50 minutes, 1988.