I find it odd reading posts like the OP because it makes me realise how the CMS world has changed from the early days to the point that people now expect to have every aspect of the system laid on for them for free - backend database-driven system handles content and skin/template/theme/whatever deals with the design and hey-presto - web design and development without any design or development!!
When I first found CMSMS I was tearing my hair out because I knew I had to offer clients a system they could update themselves but all the other solutions forced my hand as a designer because they were so damned hard to design on top of - with Joomla, Drupal and the others you HAD to have a premade skin because creating one was such a bind but then all the sites looked the same. Only CMSMS made it possible for a professional designer to create a great design and bolt it seamlessly onto a PHP engine.
So my advice to the OP would be - CMS Made Simple really isn't about skins or templates - it's software for those who understand the parameters of professional web design and can learn Smarty and blend the database element together with their own designs. And people who say
Unless I want to learn to do all of the coding to make major changes to the templates I have found
have missed the point - that it IS aimed at people who not only 'want' to do that but who's profession is to create designs from scratch.
Of course, that's not to say you can't use a pre-made template and, as RonnyK points out, there are a fair few available on the themes site, but I can't see the dev team ever wanting to make 'free templates' a core interest of the project.
Hope that helps.