The basic requirements of good SEO is to build a good website that is useful to real people. Thankfully the days of gaming the system are largely gone.
A great way to learn about SEO is to analyse sites with free, online SEO analyser tools. Then you can read up on all the individual criteria they judge a site by. I learned a lot more about SEO by using these tools. This article has a list of SEO tools you can use. They are also a useful way to critique your website to ensure you’re following best practice (e.g. all images have alt properties, only one h1 tag per page, etc.).
Would you need to change the locations of the site’s existing pages? If they already have a lot of links coming in from the outside I can understand why they’d be nervous about a complete re-design. If you are just changing the theme and some behind the scenes stuff and the URLs of each page are staying the same then this might make your prospective client a bit happier.
Two useful quick tips for SEO: Keywords. Use keywords appropriately in the text, making sure you also use synonyms and phrases that customers might search with. Scatter them in a reasonable manner through the page, making sure it still reads well for your audience and doesn’t seem like it’s being written for a robot! Treat each page separately for SEO because you never know which page is going to be the one a user lands on first.
Also, ensure the site has SSL encryption and that your http:// site is redirected to https://. Google is currently boosting rankings for https:// sites to encourage a more secure web.
cheers,
Ali