Yea the link has precompiled kernels, go for i686.
On my p3 1.13g it takes around 20-30 minutes, but it'll depend on how many modules you've selected.
why is that 3 choices of menuconfig, old config and xconfig???
They're just different options you can use for configuring the kernel, menuconfig is a ncurses based interface, old config automatically detects your previous configuration then gives you options on new features, xconfig an X GUI frontend.
IIRC there's also a GTK (gconfig) and a QT one.
Personally I recommend menuconfig, I find it easier to use.