With a fresh install of Red Hat 9 on a Dell Dimension 4600, the only video mode that would work with XFree86 was 640 x 480, which is ludicrously big on a decent-sized monitor. Changing the config didn't do anything, even though the config was well within my monitor's limits.
The solution was to go into the BIOS setup and change the Integrated Devices (LegacySelect Options) / Onboard Video Buffer setting from 1 MB to 8 MB. I'm not sure what the tradeoff with other aspects of the system is, but X nicely starts up at 1280 x 1024. Apparently, this is the solution for other Dell models as well, including the Optiplex GX260; mine had Dell BIOS Revision A08. Also, it seems to be the case that the problem is general to XFree86, although it manifested for me under Red Hat 9.
Thanks to Erick Tonnel at Dell, who kindly provided the solution here:
http://lists.ze-linux.org/2004-02/msg00154.html