It is all fairly relative. Most average people cannot tell the difference between 30fps and 100fps. But, many people can, I personally find that as long as I get 40fps as the minimum or over, it is fine generally.
However, each game is different. For example in one game 30fps will seem choppy and like a slide show while in another game, 15fps will seem smooth. I am refering to Flight Sim 2002 for saying that 15fps is smooth. It all depends on how the game and the game's graphic engine was designed. So basically take it as a case by case basis, but in general I recommend to people that you don't want your fps to drop below 20-25fps at the lowest.