Checked with my buddy, they used to book guides in Vilamoura at the harbor in person as well without going to the Azores. Possible sharks there are mako, blue, hammerhead and tiger, all c&r. Marlin and tuna are also possible, but they were usually after sharks.
He said they never had a bad experience with guides, all of them worked their asses off to get people their fish and they always had a great time.
No idea how long you are there, but might be interesting to see if you can find cheap flights to Spain (or drive), send the wife to Barcelona for shopping and culture and book a catfish trip on the river Ebro. The European catfish are nothing like those in the US, they get over 7' long and triple digit weights.
http://www.ebrofishing.com