How do you check the exact framerate in the game? (I'm interested since so far I can only describe it in terms of smooth, slow and painful-nearly-unresponsive-slideshow)

use fraps,you will be able to find it free on the net somewhere

I'll second FRAPS - I'm pretty sure there's a console method as well...

Well, maybe not. In Oblivion, you would use ~ (tilde) and then "tdt" to get the frame rate to display, but that command isn't in Fallout 3's console. Most of the Google search results end up saying "use FRAPS" (or some sort of video card monitoring tool like the Riva tuner or EVGA Precision software).

Thank you.

So, now I know I get periodically get 5-6 fps and almost never over 30 fps. That is on Medium settings and around 500/400 window. Seriously...

Playing in a window, you will almost always get lower performance then full-screen.

In FO3, with my 8800GT 512MB, I would generally get around 30-40 FPS in most areas when running 1600x900 full-screen. That was mostly medium-ish settings. On the GTX 460 1GB card, I get pretty much a solid 60+, sometimes dipping into the 40s-50s, with most all settings set to high-ish end (especially actors and objects being visible at a larger distance). The major hitches are when I cross an outdoor cell boundary and it needs to load in an additional 3 or 5 cells (and the only help for that is a 10k RPM SATA or a SSD).

I'm running New Vegas at at 1680x1050 Ultra on an 8800GT at full 60fps (vsync) outside and an average of 40 around NPCs. Everything is cranked to maximum with the following exceptions:

AA is 4x
Water reflections & refraction are turned off.

Smooth like butter! Not bad at all for a 3 year old machine. Intel Q6600 2.4ghz, 4GB of ram (320GB 7200rpm primary hdd and a 1.5TB 5900rpm secondary I use for archive storage and Fraps captures)
This is also using the d3d9.dll fix - before that I would get 60fps outside and as low as 8 when more than a couple of NPCs were on-screen.

The d3d9.dll 'fix' forces an earlier, more primative video mode.
Therefore, your 'cranked to maximum' and 4xAA are phoney.
Instead, you should use all the latest drivers (including DirectX), disable AA and Vsync within the game and run medium or low settings if required.

@Magnificate
Do you have nVidia or ATI?
Important to launch the game with high-performance settings in the nVidia Control Panel or ATI CCC.
Do not set to force vsync, AA or AF. Always set 'application controlled'.
Set for max performance, all variables.
Disable Win7 Aero effect before launching.
Play full-screen using very modest resolution and game video preset, no AA, maybe 4xAF.
Once you establish smooth, fluid performance at meek settings, you can begin to experiment with higher settings.
On my rig I get 60fps minimum - and avg. & max. are much higher.
I use 1680x1050, no AA 4xAF, no vsync, medium settings.
Very smooth and fluid, and looks fantastic too.
Regards

"Earlier, more primitive" is a misnomer. The Gamebryo engine maxes out with Dx9.0c, but Obsidian and nVIDIA managed together to create broken internal communication in Windows 7 particularly, about Dx9, and since the Dx10 Dx11 functions aren't adequately backward compatible, a variety of faults combine to create slowness for the more recent of nVIDIA's high end hardware.