Depends on the genre. For the likes of turn based strategy or adventure games the FPS only matters for the mouse movement.

Edit: I'd say that 20 fps is the minimum for comfortable UI interaction, but it's possibly to get by with less.

I find that it tends to vary based on the genre / content:

Strategy games and some RPGs, I don't mind too much if they go down to (or even below) 30 fps.

Most shooters and faster-paced games of other genres I dislike playing at below ~45 fps.

Particularly fast-paced games, 60 fps or more.

Windows desktop, 120 fps. My monitor switched to 60hz once after running an old game recently (without displaying that it had changed refresh rates) - I instantly noticed the jerky motion of the mouse cursor. *shrug*

Movies at 24 fps are painful to watch whenever there's fast action or panning shots, and not particularly pleasant the rest of the time.

60 is the gold standard and 30 is Bronze. Anything below 30 is failure. 120 is platinum, 240 is...going well beyond the call of operations.

I really don't know. I've had SOME experiences with framerate, but not anything in-depth. Maybe it's just me, but the FPS has be single-digits (or close to) before I actually notice it.

Since my first Windows machine with a Voodoo 3 3500 in 1999 up to my current Athlon 64 x2 with a Radon 5750 (which I've had for a few years), I can't recall ever having played a reasonably demanding game at over 30 FPS (unless I turned all graphics options way down).

I much prefer playing at high settings and 5-10 FPS than low settings and 25-30 FPS.

Something tells me most next-gen console games will only have one or the other (and some will have neither...)

Depends a lot on the game in question. If it is a fast paced action game, I prefer to have a higher FPS (still depending a lot on the game). 60 FPS is what I strive for, I can play a game at about 20 (though it obviously impacts my enjoyment of the game).
Inconsistent FPS is more annoying than low FPS though.
For turnbased strategy games, I can accept far lower framerates.

Yep. Id proved that most people don't notice/care, they just want their slide show to have more pretty.

When you play it's not only about what you see but control responsiveness as well. The difference is obvious - try rotating camera.
The passable framerate depends on the game. For one 55 fps is unacceptable, for the other 30 will do.

I never cared for FPS. I just change the graphic options until I think it feels okay. The only two games where I know my FPS are GTA IV and Tomb Raider 2013 (what a bad game!), because they have their own benchmark tools to test your settings. In GTA IV I turned everything on maximum and the game told me it's running with 60 FPS. Is the benchmark tool broken? Well... The game is not stuttering, so I'm happy.

In Tomb Raider I learned something about me. I turned everything on maximum and the benchmark told me it was running between 15 and 30 FPS, with an average of 25 FPS. I didn't like it. I changed the depth of field (it was simply too much) and turned off Tress FX (the hair animation), because it looks terrible and is very demanding. My FPS went up to 25-40, but I still thought parts of the benchmark did not look good. I changed the AA mode (haven't seen any difference) and the game went up to 30-45 FPS. That's where the benchmark looked good to me. So I guess 30 FPS is my personal minimum for games like Tomb Raider.

It depends on the game, but as an old console gamer i am fine if it runs without stutter

I prefer 60FPS and always tweak as much as possible to get it, I even have a tag that says 60FPS+ on Darkadia so I can keep track of what games actually can run it (mostly about the game, not because of my computer). That said it depends on the game and its engine and my mood. I've no problems playing Heroes III (one of my favourites) which run at 10FPS constantly but animations are very stiff in that game, it's likely that and because I played it since I was 10 years old. Heroes IV on the other hand where movements became more 3D it bothers me more but it's still playable. I still prefer 60FPS and I'm willing to lower all graphics except resolution if the game supports 1080p, if it still runs lower than 30FPS I put the game into my backlog and wait for an upgrade.

I agree that consistent framerates is as important as high framerates, that's why I always recommend frame limiters and VSync. No point going over your monitor's hertz setting. It's a useful site but I find doing tests on that one becomes inconsistent. I notice framerate drops much quicker in games than that site.

I notice the difference, but with most games I don't really mind it, as long as it is 30 fps or over.

Depending on the game, 20 fps may be passable. Actually, I'd say that if the framerate keeps changing all the time is more disorientating than if it is e.g. constantly a bit lower. (And yes I mean only the framerate, not actual game speed. Game speed should always remain the same regardless of the framerate, of course. I can recall only some ancient game like Test Drive 3 where the framerate and game speed seemed to be linked. It was quite hard to play as the speed of the car kept changing all the time. :))

The next question is, what graphics options do people lower first in order to get the framerate higher?

For me it usually goes in this order:

1. Antialiasing (MSAA, CSAA etc.). I usually disable this altogether, if I am not happy with the framerate. I can spot the difference, but IMHO the visual change is not big enough considering the big performance impact that antialising can many times have.

2. Motion blur. In fact, I many times prefer this off anyway, even if it doesn't affect framerate.

3. Any other oddball ones which have a big hit, but I can't really see any visual difference. Like that übersampling option in The Witcher 2, what the heck is that anyway?

4. Resolution. I usually rather lower the resolution from 1920x1080 to 1366x768 or even 1280x720, than touching rest of the settings.