GRUB allows you to choose the VGA definition it uses when booting. 
(Note: this does not affect the definition in Xorg).

You need to add the option vga=xxx on the kernel stanza in the file /boot/grub/menu.lst. 

Of course, replace xxx with the video mode you want. Your kernel stanza will look like this: 
kernel /boot/vmlinuz-2.6.18-6-686 root=/dev/sda7 ro vga=791

Here is a list of the available video modes:

Colour depth640×480800×6001024×7681280×10241400×10501600×1200
8 (256)769771773775
15 (32K)784787790793
16 (65K)785788791794834884
24 (16M)786789792795