We did this a couple of years ago, tho I don't think it was the same biz. They took off from the pier next to Fidos. It was a blast, they gave us about a 25 minute ride down past Banyan Bay and back, really fun to see SP and the reef by air.
I have done parasailing twice with extreme adventures and would recommend it.
Once was solo with I totally loved and the second time was with someone who was scared of heights which I was dubious about but the ride was smooth and the guys in charge eased her fears. She quite enjoyed it and was not scared once we got in the air.