Hello everybody,
I'm a former Google, Inc. employee and I can tell you that SEO is not wizardry, it's not some semi-science and especially nothing to be a genius in order to comprehend how Search Engine Optimization works.
First of all - it's a matter of content.
Second - it's a matter or pure arithmetics, algorithms.
Have your content written down before you think of website design.
Second - decide what your website DOES. It's like buttons

What does this button do?
Third - Design - Form follows function.
Don't imagine your website like a sweet little frame and then when you want to add more content nothing fits in. So, imagine your website like it's something made of chewing gum... should never be the same, should always offer new experiences - this brings me to the WOW or surprise factor.
In this order you should consider things for a better SEO:
1. Find a guy who can write clean code
2. Pick up your color scheme
3. Write down your copyright
4. Asses images of the site or have your images done especially for the site, talk to an illustrator, graphic guy, designer, etc.
5. Imagine the typography - headings, normal paragraph text, subtitles, chapter signs, bullets, etc.
6. Now back to content, create each page and carefully craft it on paper, visualize it so you will be able to properly describe it to the web designer, also keep it simple and let the designer do what he/she does: design. Don't screw with designer's work, that's why they studied DESIGN, so they can offer services and DESIGN stuff. Don't be the designer's controller, let them do their job. You can't design websites better than they do, you can only make suggestions and accept their refuse, maybe that's a real bad idea.
7. Follow-up with the designer every three days, let him/her breathe, don't call/write every day, it's so annoying.
8. When site get into shape don't look at it everyday like 10's of times, your original idea might disappear, and THAT could be the best idea you might come up with. Plus that the designer might charge you additionally for the modifications.
9. At this point you'd rather prepare for the website launch, advertise it, do some viral stuff, tell your friends, create a "current", do what you exactly do before your first child get born: be excited.
10. Keep your website up to date, keep posting new content. Google loves fresh unique content. It doesn't matter what stupid stuff you want to post as long as it's your own generated content.
11. Drive some Social Media Campaigns or SMM, SEM, or other triple-letter abbreviation smart name thingy.
Don't bother about inbound linking, make sure your website is easy to navigate, has an excellent typography and website architecture, it's nice for the human eye, the code should be clean, get gorgeous images, crisp and coloured, let your visitors' eyes go around the site, not just see the logo and the menu... this brings us to visitor's engagement to the site.
Give the visitor something to do, they all get bored at your blah-blah about how old on the market and reliable your company is, they don't care about that. They came there to see some action, oh yes! ACTION! Call-to-action! Do this, click here, buy that, see that... they prefer call-to-action buttons to your multitude of text and company history, philosophy and/or view, business ideas... really, nobody cares about that.
Visitors need your services and your contact data. The rest is just pages you can woo them with, make their navigation pleasant. It's like they are in your home: you're supposed to make them feel welcome and special.
Some companies offer you weekly SEO services, or they promise you number one in 2 weeks or something... People, believe me, nobody can guarantee such a thing, not even Google. When you hear about weekly/monthly payment for SEO just turn to the opposite direction and run as fast as you can - because it smells like fraud.
I could go on and on about the other aspects of SEO, but it's already too much

YES, so is not about the on/off-site optimization. It's about original content, typography, user experience and architecture. The rest will come with your hands off: SERP, inbound linking, referrals...