1. Use Illustrator, etc. to save your eps file to a jpeg. Generally, a quality as low as 3 looks fine, but the files get small enough using a quality of 7.

2. Download the jpeg2ps program at: http://www.pdflib.com/download/free-software/jpeg2ps/

3. Extract and put your eps files in the same directory as the executable. Command usage is "jpeg2ps YourFile.eps > YourFile.jpg"

4. The program puts an eps wrapper around the jpeg data, and makes really small eps files (e.g. I converted a 4Mb eps to 190 kb.)

5. If you follow these quick tips, your ArXiv submission will be a breeze. Leaving you plenty of time left over to pontificate on thy mysteries of the universe; like, why the arxiv wouldn't just accept your 100 kb pdf file to begin with?