I completely agree with you when you say..
"In my opinion the SEO consultant who will bring the most value to a company will be the one who learns the most about that company's current business, current products, current goals and current capacity... and then identifies ways to match them to opportunities that exist on the web."
And this is exactly the type of business I want us to be, so how would you recommend learning about these above mentioned factors and more. Apart from researching there site and industry ( which comes later) assuming they are not a client yet.
It seems to me that a well designed in depth questionaire would scale very well and would mean that before you start looking deeply into someones site ( which takes alot of time ) you can use questions carefully constructed to serve lots of purposes.
Then of course come your research more talks with the client and eventually a proposal/ business plan.
but it seems to me that the first step is to make them think through a set of questions
it shows that they are commited and it should be very usefull for everyone involved