Well there's always the Prince of Persia/God of War-style tutorials. Tell you how to do something and kill you dead if you do it wrong. Of course this method makes some players cry so...
But yes, despite the benefits of such an introduction, the flaws show with more and more games doing it. You want an action-packed opening but can't make things too hectic for the player before they learn how to walk. A separate tutorial can help avoid that and prevent repetition on repeat playthroughs (Zelda, Kingdom Hearts, etc.). One of the best examples of these I can think of would be Star Fox 64, which had a medal score like any other stage and an early Star Wolf cameo if you scored high.
Story-wise, you can't expect Call of Duty to pay any attention to narrative sense, their main audience doesn't care why they're shooting people, just that they are. Arkham Origins is a prequel so there's not much to bring you up to speed on, but aren't there dossiers for each villain anyway?