Even extremely repetitive games can be fun, so that's not certainly the best measure of fun, although I think in general, more variety is better. But many games arrive at their variety simply because they're simplistic design allows for it. Puzzle games and online fps are some examples. When it comes down to it, most fps is simply lining up a target in the center of the screen and pressing the fire button. Most games are more complex than this these days, but I still go back and play doom every once in a while, where it's NOT more complicated than this - and what do you know, after all these years, it's still fun. Even replaying the same levels over again. But I'll tell you, I'll bet no runthrough of a level goes exactly the same way twice - even moreso when playing against other players. So the variety comes not because new gameplay is added, but the gameplay itself can vary, and quite widely too.
This is where many rpg or adventure games fail also. They may have really great story, or leveling up might be fun, but if you play through it again it is generally so rigid you get pretty much the same experience. And if you talk about your experience with someone else, one person may know a better strategy for tackling a boss, or have a higher level party, or solved one puzzle much faster or earlier in the game than another player; but on the whole these two experiences are nearly the same. More open rpgs like fallout don't have this problem. Then again, it can still be a lot of fun to follow along a great story at your own pace, and feel like you are in control of it. So you can't judge fun by this metric either. As far as story goes, I think that the more freedom you give the player, the less story really matters, and the more restricted the gameplay is, the more story matters. I play a lot of adventure games, but if the story stinks I will turn it off. If the puzzles really challenge me in a good way, I may perservere, but I would not consider it a good game. Whereas, if I play, say, Call of Duty 4, I could care less why this group of people are the bad guys, just tell me who is bad and let me kill them. Different sorts of games really have a different metric for what is fun. It really depends on what kind of response you are going for. Game design is a medium for communication - if whatever feeling it was you try to convey through a game gets across, then I would say it was a success. Hopefully, that message is fun and rewarding for people to experience, but that's not the only criteria either.
