For Cabo San Lucas:
Best beach for a half-day visit: Playa Medano, fronting the Bahia de Cabo and the Sea of Cortez is an easy taxi ride from the marina.
Best beach for active types: Same: all sorts of watersports rentals are on hand at Playa Medano.
Quiet Beaches: (Car renters only) Head out to the "corridor" between Cabo San Lucas and San Jose del Cabo, which rings the Sea of Cortez, and pick one! Closer in: Playa del Amor, otherwise known as "Lover's Beach," is snuggled between rock formations near El Arco and fronts both the bay and the Sea of Cortez; you need to hire a water taxi to drop you off and pick you up (they're easily available in the marina) and there are no facilities so bring a picnic.