"...and will be working with an external agency."
The external agency should have their own consulting strategy.
If you need information about how to view your website from a consultant perspective, Danny Dover's book is a good resource:
http://www.amazon.com/Search-Engine-Optimization-SEO-Secrets/dp/0470554185/ref=sr_1_1?ie=UTF8&qid=1313596634&sr=8-1
Everyone has their own method.
-I'd start with a quick site audit. Make sure you have content that people will link to, a solid graphic design, and a good UX.
-Determine who is your target audience.
-Decide who are your main competitors.
-Research what your customers are calling your services.
-Research what keywords your competitors are targeting.
-Find out what variations of these receive the most traffic with the least competition (SEOmoz Pro Tools/AdWords Keyword Tool/Others)
-Pick your metrics to track. Have a way to separate web conversions from other sources (a separate email, phone #, feedback form, etc.)
-Fix your internal site issues (canonicalization issues, Meta Robots, no Meta Description, etc.)
-Optimize your site for your targeted keywords and a strong UX.
-Start gaining external links
-Continually test keyword variations and add new content
-Compliment organic campaign with a PPC campaign (optional, but it's a good way to quickly test keywords).
I'm sure I left out several steps. But that gives you an idea.
And there are many ways to complete each step. Many ways to build links, do competitor analysis, perform keyword research, etc.
If you ask ten people, you're going to get ten different answers. I'd find an external agency that you can trust and let them do it their way.