出自の違いですね。
diff-lcs は perl での実装を移したもの。
argorithm-diff は、rubyによるWiki実装であるTikiから切り取ったもの。
（登録者はTikiとは関係ありませんが。)

採用しているアルゴリズムも異なるかもしれません。
代表的なものでも数種類あるので。
双方に対して、速度とかテストしてみてよかった方を採用しては？

将来的なメンテナンスという面では、diff-lcs かな。