> I've run into cases far more often where I need to maintain insertion order than sort order, but I'm not confident about whether this is due more to the type of stuff I work on or if it's just a more common requirement in general.

I've had the exact opposite experience, so I'm guessing it has a lot to do with the type of stuff you've (and I've) worked on.