I wouldn't worry too much about making the examples trivial. That just makes it easy to learn! There are probably lot's of good orders, but I'd probably go something like:
IMO character classes are quite an advanced feature (or at least confusing for beginners) because of being character orientated. They also don't tend to very useful unless you've already covered repetition.
Yes - in the Character classes chapter you had just introduced the negate operator, then in the next example use the beginning operator, which happens to be the same character in a different context. That might be a leap too far. Great resource!
- Literal strings - Optional characters - Optional strings of characters (using groups) - Alternations (using groups) - Repetitions (using groups)
Then move onto to things like character classes.
IMO character classes are quite an advanced feature (or at least confusing for beginners) because of being character orientated. They also don't tend to very useful unless you've already covered repetition.