The Sheraton Algarve is an excellent property on a cliff overlooking the oceans, with an elevator that takes you down to the nice beach area. The buffet breakfast, which I believe is included, is lavish and not to be missed.
Villa Joya, the only Michelin 2-star restaurant in the country (at least when I was there), is excellent, although difficult to find.