just iterate on the new Items doing gets on the old Items. I recommend adjusting types at the beginning of the code, in case you need to use the information again later on

public static void AfterUpdate(Map<Id, SObject> newItems, Map<Id, SObject> oldItems) {
    
    Map<Id, Lead> mpNewLead = (Map<Id, Lead>)newItems;
    Map<Id, Lead> mpOldLead = (Map<Id, Lead>)oldItems;
    List<Task> newTasks = new List<Task>();
    
    for(Lead updatedLead : mpNewLead.values()){
        if(updatedLead.ProductInterest__c != oldItems.get(updatedLead.Id).ProductInterest__c){
            Task newTask = new Task(
                Subject = 'Follow up with Lead, their Product Interest was updated',
                Status = 'Not Started', 
                WhoId = updatedLead.Id,
                OwnerId = updatedLead.OwnerId,
                Priority = 'Normal'
            );
            newTasks.add(newTask);
        }
    }
    Insert newTasks;
 }

just iterate on the new Items doing gets on the old Items. I recommend adjusting types at the beginning of the code, in case you need to use the information again later on

public static void AfterUpdate(Map<Id, SObject> newItems, Map<Id, SObject> oldItems) {
    
    Map<Id, Lead> mpNewLead = (Map<Id, Lead>)newItems;
    Map<Id, Lead> mpOldLead = (Map<Id, Lead>)oldItems;
    List<Task> newTasks = new List<Task>();
    
    for(Lead updatedLead : mpNewLead.values()){
        ifif(updatedLead.ProductInterest__c != mpOldLead.get(updatedLead.Id).ProductInterest__c){
            Task newTask = new Task(
                Subject = 'Follow up with Lead, their Product Interest was updated',
                Status = 'Not Started', 
                WhoId = updatedLead.Id,
                OwnerId = updatedLead.OwnerId,
                Priority = 'Normal'
            );
            newTasks.add(newTask);
        }
    }
    Insert newTasks;
 }