Can contribute slightly - best beach in my opinion is Falesia but you have to walk there across the river round the back of the marina as it were. There is no road. The beaches at Vilamoura and Quarteira are wide and sandy, easily walkable.

Yes there are plenty of boat trips from the Marina but some may not be running in low season (May) so best check when you arrive.