Free-form notes sound useful and fairly easy to implement. Making them searchable would add even more utility.
Being able to tag contacts, and filter by tags, might also be useful. One contact might be tagged “work, chess club, engineer”, and another “toastmasters, synagogue, IT, school carpool”. And if “structural engineer” could be a subtag of “engineer”, and “school carpool” a subtag of “has kids”, that would be handy!
Tags could maybe even be used for this usecase described by @FrankLanger.