In a comment at the recent question What is the standard 2-generating set of the symmetric group good for?, it was remarked that the symmetric groups $S_n$ for $n\gt 2$, $n\neq 5,6,8$, can be generated by an element of order 2 and an element of order 3 (G. A. Miller, Bull. Amer. Math. Soc. 7 (1901), 424-426 doi:10.1090/S0002-9904-1901-00826-9). The remaining three nonabelian cases can of course be generated by a pair of elements, but these are cycles of length $5,6,8$ respectively. What is the best that can be done in these cases, and is there a conceptual reason why these are exceptional? (eg the presence of the nontrivial outer automorphism of $S_6$? Or some action on an exceptional combinatorial object?)

ADDED By 'conceptual' proof I mean something more like 'structural', or the analogue of what in combinatorics is a 'bijective proof'. There should be some actual construction for the generic case that clearly breaks down for the small cases, due to a lack of space. Compare for instance the deep understanding of what goes wrong with the sort of handle moves that happen in high-dimensional topology, when we go down to dimension 4, and then why the replacement there will not work in lower dimensions. Simply counting two sets and noticing they have the same number of elements isn't the sort of thing I want. Nor do I want a proof that just writes down a pair of generators and checks they work, but of course I do want to see said generators.