The above cover all of the SE without so much of the M
My first question is always "What is your USP?" or "What does your company deserve to be ranked in the top ten available resources for?"
If they can't answer that to satisfaction then I know that the rest of it is going to take more resources whereas a naturally brilliant product/resource is far easier to promote - especially in terms of link building.
"Are you willing to change the actual content of your site in order to attain higher rankings?"
It is amazing how many companies want some magical solution that gives them top rankings without changing a thing. I tell them that such magical devices exist, and the most easily applied one is called Pay-per-Click.
"What tracking systems do you currently have in place?"
"What visitor data can you provide to highlight which referrals are your best converters?"
"Do you have an in-house development team?" You need to know whether the best solution for the client would be for us to do it for them, or for us to train their existing staff.