"that Xpath expression works as an OR. What would the expression be if I wanted to AND the selected Contact Types together, before retrieving Contacts"

You would need to use a different method. For example, another way to achieve the 'OR' functionality is to first do a retrieve of the ContactType records selected in the Helper record - this will give you a 'List of Contact Types'. Then create an (empty) List variable of Contacts. Then loop through your list of Contact Types and retrieve a list of matching Contacts for each value, and add (not set) the results to your Contacts List variable. When the loop is finished you will have a list of Contacts matching any of the selected Types.

For 'AND' functionality, you can do something similar, but for each loop after the first retrieve perform a list operation to do the intersect between the existing list and the new list to retain only those records that exist in both lists. The last action of your loop should be to 'set' the List valiable to the current value of the intersect list so it is ready for the next loop.

One way to achieve this is to use a helper entity with reference set links to the Contact entity and the Contact Type entity, so you open a record in the helper entity and can select one or more Contact Types (perhaps via checkbox selector widget).

Then have an on change microflow when the Contact Types selection is changed, to retrieve all matching contacts. Link the result set to the helper entity record and use this reference to display a grid of all the retrieved contact records.

You will then also need some further workflow to clean up the temporary helper entity records, or link then to the current user and reuse the existing single helper entity for each user if it already exists.

Edit after comments: No, the helper entity is a new entity you create in your domain model with reference set associations to the Contact and Contact Type entities. The existing associations between them should remain unchanged. Your new helper entity might also have an association with your Account entity so you can link it to the current user.

Then, to search your Contacts, instead of using a standard data grid, create a microflow and link it to your menu. In the microflow, first retrieve an existing helper entity record for the current user - if found use it, if not found create a new record. Open the record found/created in a data view of the helper entity. This form should contain the reference set selector/checkbox selector to accept the search criteria, and below that a data grid of the Contacts using the association between the helper entity and Contacts as the data source.

Then add the On Change microflow on the Contact Types selector to retrieve the contact records matching the types checked, then update the helper entity (with refresh) to set the search results to the association between contacts/helper entity. I hope that's clearer. Once you get your head around this, it's quite a useful method for displaying more complicated search results, or even a menu of standard searches.

Edit: An example of the retrive from database X-path constraint might be

[MyFirstModule.Contact_ContactType/Name = 'Value1' or 
MyFirstModule.Contact_ContactType/Name = 'Value3']

Alternatively, you could do something like this: where the x-path is [MyFirstModule.Contact_ContactType/MyFirstModule.ContactType/MyFirstModule.HelperEntity_ContactType = $HelperEntity]

Note that for this to work, you need to commit the helper entity as the first step of the OnChange operation.