Sort the files by the key field prior to comparison where the key field will be first followed by the remaining fields in ASCIIbetical order (potentially very expensive upfront operation)

If you have the unix-style "head", "tail" and "sort" utilities, you may be able to reduce the cost by opening the inputs this way:

$old_header = `head -1 $old_csv`;  # split that later
# get $new_header same way, if it's different from $old_header

open( OLD, "tail +2 $old_csv | sort |" ) or die $!;
open( NEW, "tail +2 $new_csv | sort |" ) or die $!;

# proceed with interleaved reading as planned...
[download]

Of course, this assumes that each row of csv data does not contain newlines, which may be inappropriate. If there may be newlines within some data fields, you'll need to parse the csv first, then sort; in which case you might consider storing key values and byte offsets/lengths in a hash, so you can sort the hash keys, and rewrite the data records to a sorted file by seeking and reading each record in turn.