In my opinion, the state should -- retroactively if possible -- require that anyone who was admitted into a university program, public or private, in which legacy plays a role has to note that on any resume. So Joe Schmoe who went to Stanford and got a BS in Comp Sci, will have to write:
Joe Schmoe, BS Comp Sci at Stanford (note: Stanford uses legacy admissions)
on their resume. To not do so would be a crime, because it's fraudulent by the new law requiring legacy admissions to be correctly advertised.
Universities will quickly end legacy admissions. Moreover, the state should probably investigate and be able to label universities as having legacy admissions.
This law would apply to anyone who wants to do a job in california.
This would end legacy admissions overnight, while not violating anyone's freedom. Universities would be free to admit students by legacy and grant degrees. Students would be free to tell employers about the degree they've earned, but california will make sure that the future employer has a full picture of the sort of institution from which they graduated.