Se vuoi davvero definire la somiglianza nel modo esatto che hai formulato nella tua domanda, allora dovresti - come dici tu - implementare il calcolo della distanza di Levensthein. O nel codice calcolato su ogni riga recuperata da un DataReader o come funzione di SQL Server.
Il problema indicato è in realtà più complicato di quanto possa sembrare a prima vista, perché non si può presumere di sapere cosa condiviso reciprocamente elementi tra due stringhe possono essere.
Quindi, oltre a Levensthein Distance, probabilmente vorrai anche specificare un numero minimo di caratteri consecutivi che devono effettivamente corrispondere (per concludere una somiglianza sufficiente).
In sintesi:sembra un approccio eccessivamente complicato e lento/dispendioso in termini di tempo.
È interessante notare che in SQL Server 2008 hai la funzione DIFFERENCE che può essere usato per qualcosa del genere.
Valuta il valore fonetico di due stringhe e calcola la differenza. Non sono sicuro se lo farai funzionare correttamente per espressioni composte da più parole come i titoli dei film poiché non gestisce bene spazi o numeri e pone troppa enfasi sull'inizio della stringa, ma è comunque interessante predicato di cui essere a conoscenza.
Se quello che sei davvero cercare di descrivere è una sorta di funzionalità di ricerca, quindi dovresti esaminare le funzionalità di ricerca di testo completo di SQL Server 2008. Fornisce il supporto del Thesaurus integrato, predicati SQL fantasiosi e un meccanismo di classificazione per "corrispondenze migliori"
EDIT:se stai cercando di eliminare i duplicati, potresti esaminare SSIS Fuzzy Lookup e Fuzzy Group Transformation. Non l'ho provato da solo, ma sembra un vantaggio promettente.
EDIT2:Se non vuoi scavare nella SSIS e hai ancora problemi con le prestazioni dell'algoritmo Levensthein Distance, potresti forse provare questo algoritmo che sembra essere meno complesso.