If your file are sorted in accordance with the comparison key, then you can iterate through the two files in parallel. This can be very very fast. Just a couple of hours ago, I compared two 100-MB files this way, it took less than 3 seconds to run.
$time perl compare_files.pl
Even if they are not sorted, this might still be the solution: first to sort both files and then read them in parallel. The only difficulty is to get the parallel reading really correct.