I think this challenge can be approached using string collection variables. It's tough to describe an imagined Flow, but I think it'd go something like this:
Fast Lookup for Custom Metadata Records
--> Loop over Custom Metadata Records
-----> For each record, add its key values (City, State, ZIP) to individual collection variables - i.e., one collection variable per data point you want to compare.
Source your Contacts (could be a Fast Lookup)
--> Loop over Contacts
-----> For each Contact, make a Decision
--------> If each key data point collection variable (City, State, ZIP) contains the
value present on this Contact, update the data on this Contact as desired.
Perform a Fast Update of your Contact list.
I don't think you'll be able to approach it as comparing a list of addresses to a list of addresses; Flow doesn't have Address as an first-class type. You could do that in Apex with a Set of a custom class that implements
hashCode() (although it wouldn't be an especially natural idiom there either).
Breaking it down into specific data points and ANDing criteria (
listOfCities CONTAINS contactsCity AND listOfZIPs CONTAINS contactsZip AND...) is going to fit the bill for this application.