Sort the files first:
$ sort file1 > file1.sorted
$ sort file2 | diff - file1.sorted
Also, although I personally discourage this sort of thing, if you are using bash and this feature is enabled on your system you can avoid the temporary file by using a process substitution:
$ diff <(sort file1) <(sort file2)