Well, I've got an 800mhz DURON, Geforce 4 MMX (128mb), and 640MB of system RAM, and my machine runs the game pretty damn well considering. I'm
averaging about 15fps with most of the settings turned to maximum!
Over big cities, it slows down to about 10fps, but flies better if I turn down the Autogen. Over regular terrain, I sometimes get frame rates of up to 40fps.
This is running FS2002, so I don't know if there's any big differences in frame rates with FS2004.

The game certainly looks great on my machine anyway.