Solutions that could not have been concieved by the average student
It is important to realise that many more solutions can't be concieved by the average student than we usually realise. Even solutions we think are quite routine can seem like strokes of genius to students new to the area.
Students often say to me, "I can follow the lecturer's proof/solution, but I have no idea how I would come up with something like that myself." And they really can't. In first year it's integrals and proofs about subspaces they struggle with. In second year it's "basic" proofs about limits using the $\epsilon$-$\delta$ definition. The problem is that our insights are based on a fairly deep understanding of the area and experience with lots of these proofs which has given us a familarity with the sorts of things that might help. The students do not have this experience, so they can't imagine even things that to us seem basic.
What the purpose of showing a solution is
I think before we answer the question, we should probably consider what the purpose of showing a solution is at all. Is it to convince the student of the truth of a statement? Is it to show them how to go about coming up with solutions? Is it to show them the patterns of argumentation that are acceptable in your discipline? Is it to gain an appreciation for the clever method of solution? Or some combination of these? Each of these purposes will give you a slightly different approach to presenting solutions, though they will overlap.
If it is students presenting the solutions, what is the purpose of that? Is it so that they get better at their communication skills? Are the students they present to supposed to have come to an understanding already, or are they supposed to use what the presenting student does to understand? Is it the correctness of the solution that is being assessed or the effectiveness of the presentation? Is the effectiveness judged by how the other students understand or on the structure of the solution itself? You need to consider these things so you can advise students on what sorts of things you want them to do when they present, so you can choose what sort of feedback you give them, and so you can decide when to intervene.
In most courses, the ultimate goal is usually to get students to solve problems on their own. Also, from my above observations about students, they need a lot of support to learn to do this. Thereforre, in my opinion the main reason for showing any solution is actually to help the students learn how to solve problems themselves.
In light of this, I have some suggestions for things you can do.
Firstly, for all solutions, no matter how routine they seem, talk about the thought processes that help make the decision of what to do. Compare the given information to the goal, look up definitions of terms, make reference to other solutions that are similar, keep looking to the goal to see if you can do something to get closer.
Sometimes, you should try something that doesn't work, followed by some reasoning as to how you could tell in advance next time that it wouldn't work. You can also list some different things to try and make a quick assessment of them to choose the one that will work, rather than actually trying them out.
For students presenting, you can tell them the purpose is to describe how they came up with the solution, and you can make sure you ask them how they came up with the idea when they do present. You can also ask other students if they had a different solution. (I remember a tutorial when one of my students used two blackboards to do a proof, and when I asked the shocked audience if they had another way, another student came up and showed the intended three-line proof. It was a great lesson in different approaches for all of us.)
For things that really are strokes of genius, even for us who are experienced, there does come a point where you can say that people worked on this for quite some time and after a lot of false starts they came up with THIS idea, which is really a very brilliant inspiration you couldn't predict. There are still some morals for the students' own problem-solving though: they should persevere when problem-solving because you might have to make some false starts before hitting upon the right idea; more experience with solutions in a particular area make it more likely to come up with a helpful idea; going outwards to a bigger domain (like going up to 3D) can sometimes help.
The important thing for me is to be clear that you can learn about problem-solving from solutions to problems, even when it is a stroke of genius.