One other possibility that worked wonders for me - in the advanced graphics, reduce water multisampling to Low. For me, voila, stutter totally gone, and I could leave everything else ultra high on my GeForce GTX260. Your mileage may vary...
@Somian
That's a different link than mine, but in any case, the files are on the second tab on the page, under "Files". I dunno, mebbe you need to register, but I don't think so except for files > 2MB...
Thank you again, I tried that two (: The problem seems to be with the very engine of the game, including old Fallout 3, Oblivion, etc. It just skips frames...I am using a Dell Studio 1558 i7, Ati 5470. Before that I had the same problem, but with Fallout 3 on my PC ( 8600GT Fatal1ty). I guess I'm just not lucky

Even this configuration is not compatible in some way with the engine of the game. Now I just feel bad for giving money for this game. I hope at Bethesda know about the people with my problem.