Without all the constraints you have listed, this is a very simple problem. Typically, you would just import the .xls file to Access and go from there. Also, you mentioned the client doesn't know how to create a CSV file. Just do a "Save As..." and CSV is an option.
Anyway, on to your real question. There are no "Great" php-based Excel reader/writers out there. There are a couple of basic "biff" ones, but they will not do what you want.
I suggest you use a Perl module called WriteExcel/ParseExcel. In this case, you will want the ParseExcel.
I am not sure what the exact output of your file will look like, but it will be in text format so that you can read it.
You could call the Perl script using an exec() call from php when you want to parse a file.
Ultimately, this is a very complex problem that would be better served by an article on this site.
--brian