It's up to the application looking at the list of files to decide how to sort them. Apparently Nautilus uses "natural order" for numeric files, while your other tools are using standard computer sorting algorithms that sort in "dictionary order" ("a" is shorter than "aardvark" so "a" comes first "b" comes after "aardvark" because "b" is higher than "a". "1" is shorter than "100" so "1" comes first. "2" comes after "100" because "2" is higher than "1").
It's entirely possible that whatever you put this CD in will ignore everything you try to do to force the files to sort one way or another. I've got an mp3 player that sorts all songs in the order they were added to the device, no matter what. If the program reading the CD sorts by filename (In my experience, most programs do dictionary sort by filename), you can force both natural and dictionary sorting to sort the files the same way by padding the filenames with enough zeros to make the numeric parts of the filenames all the same:
00001.jpg
00002.jpg
00100.jpg
00100 (01).jpg
00100 (01a).jpg
00100 (13).jpg
Then both natural sorting and dictionary sorting will come to the same result. Automating this process is going to be hard. If you removed all the parentheses and spaces and letters from the filenames, the following script would pad everything out to 5 digits (for more or less zeros change the 5 in printf %05d $n:
#!/bin/bash
set -e
for x in *; do
e=${x##*.}
n=${x%.*}
nn=`printf %05d $n`
mv "$x" "$nn.$e"
done
This will error if the filenames have anything other than digits in them though. I can't think of anything other than renaming one at a time, or doing something like rename s/^/0000/ ?.jpg rename s/^/000/ ??.jpg rename s/^/00/ ???.jpg and so on, and that still won't work well with the extra stuff at the end of your filenames.
If you want to automate the conversion you'll probably end up completely renaming them to something else (like the timestamps as the other poster suggested, as long as the timestamp is written in descending order (year month day hour minute second) they'll sort properly in dictionary order, but if there are two files with the same timestamp you might lose one if you (or your exif processing program) are not careful.
