Social Security offers cash benefits, whereas Medicare is an in-kind benefit, in the form of health care (which in turn is distinct from health, itself another in-kind benefit). Therefore always cut Medicare first.
I think there may be come cases where this view is incorrect on the margins. But as a general principle it should be front and center in the public debate (especially given that, at the moment, the two programs are roughly equal in cost).
After all, treatment for medical conditions is nice but basic food and shelter might be preferable, if one can only have one of the two. If one can have both that is obviously better but it is worth noting Paul Krugman's point on which program has sounder finances going forward.