this might actually be a combination of things that are going on with the game, and the player simultaneously, but for different reasons.
1: the player may be learning the game to the extent of being able to master the tools they are given in a First Person Shooter becoming more and more accurate with a gun that is designed to have issues, or learning a different strategy to complete a given situation. these are all bases for player improvement (which some of the other answers have stated, or alluded to.
2: it may be to do with the difficulty curve of the game (there are multiple, but I will only talk about specifics here). as a game progresses it is expected to present more, and more challenges to the player, and by nature the player is needed to gain more, and more skill to proceed (see 1), and by virtue the game can continue to increase the difficulty of the game itself. the most common of these curves are linear increasing, increasing step function, and (one that I dislike, but is still used) logarithmic.
3: it may also be that the tools that are given to the player directly modify the difficulty curve by bringing it more toward a linear constant, or a fractionally increasing linear. though it should be said that with these new tools can also greatly increase the difficulty because the player is expected to have more of an advantage otherwise (this is where we get the step function difficulty curve where the steps are increased every time the player earns a new tool)
when all of these parts are used in tandem if one, or a couple are under-, or even over-expected then the game can easily become too easy or too difficult, or just seem that way.
like in your example of Angry Birds. as the game progresses the player is presented with different bird types that have different abilities that should conform to the given puzzle. so it is expected that the game still has a difficulty curve, but because each puzzle is in isolation of the others they must be evaluated individually instead of on a curve, and by nature the difficulty of a given puzzle is independent, but the game overall should still conform to a curve.
as a note that this answer only considers player skill, and never takes into account luck.