I have never introduced students to order of operations.  I have always received students after their initial introduction.  I always feel like receiving students after their rote memorisation of BEDMAS (or PEDMAS if you call 'em parentheses, or are very apologetic about your kin), means that when I try to let them explore they just default to what they memorised, but they cannot recall that after the lesson.  It makes me feel stuck between a rock and a hard place, but I still wonder what the initial introduction can look like.

One introduction that I have just thought of this morning, I'd like to try.  It's heavy on symbols, which I am afraid of, but I think it is basic enough that it might spawn some conversation and debate.  I just want to share it and see what you all think. I like it because I feel it introduces students to some manner of proof, and following logical principles, and I think it would be very interesting to see students' misconceptions about the order of operations.  Here goes:

Premise 1
Ask the class what is 5+12?  What is 12+5?
Can we agree that 5+12=12+5?

Premise 2 
What is 3x4? Can we agree that 3x4 is another way of writing the number 12?

Conclusion
I am going to write something on the board.  Tell me if you Totally agree, somewhat agree, somewhat disagree, or totally disagree...

5+3x4=3x4+5

Have students get in groups and say, "give me a knock down reason why you think you are right."

The agree-er- This student believes it, and would focus on the fact that 3x4 is another way of writing 12.  This student would be good to play devil's advocate with.

The choose your own adventure - This student says, "If you decide to multiply first it can work, if you work left to right it doesn't."  This is pretty easy to counter, ask them to try both ways on just one side of the equation. You get that 5+3x4≠5+3x4, "That seems ridiculous doesn't it? So which one should we choose?"

The reader - We read a book left to right, so we read math sentences left to right as well. This student gets that we need to have a common way to solve all math problems, but does not quite understand the separate operations.  (This is the student that I need help with!)

This is where I have never been and wonder how worthwhile this exchange would be.  Would students logically piece it together? Would most students be an agree-er, a choose your own adventure, or a reader? How would I encourage each of these groups to prove themselves and come to a consensus?  What questions would you ask your class in this discussion or is this just a bad introduction?

I have been thinking that I would much rather introduce Order of Operations, as terms rather than BEDMAS.  This would prepare them for algebra, and would provide a more conceptual understanding of the process.  I do not know what the progression would look like, but I assume that beginning with multiplication and addition would be the natural place to start.  Where would you go next? Subtraction?  Maybe you are thinking, "Timon you are CRAZY, this is HOW you should do order operations." Please tell me about it; I want to know.