Ok, I've found the solution (sorry for the x-post, but I didn't want people to miss it):
It seems that a fresh install (of Red Hat, at least) gets the video settings right in the kernel, but subsequent kernel builds have to have the proper settings.
In menuconfig:
under Console Drivers:
make sure the following are checked as built into the kernel:
VGA Text Console
Video Mode Selection Support
VGA Text Console is the more important of the two, but if you want to see what 'vga=###' or 'vga=ask' does when put in lilo.conf, you need the Video Mode Selection Support. FWIW, I tried using 'vga=ask' and then 'scan' when prompted, but my screen flashed a bunch of times and then hung, either at an incompatible video mode or just hung altogether.
Once your new kernel is built, you should be able to boot straight away without using 'vga=####' in lilo.conf, but the text mode is 80x50, I think. I can't be sure as I don't use that video mode. Now, this mode can be changed in the kernel by using 'rdev -v' or 'vidmode' so you won't have to muck with 'vga=###' in lilo.conf. The syntax is as follows:
/usr/sbin/vidmode <insert kernel image here> 65535
This statement sets the videomode to 80x25. (Remember, if you want this in your kernel builds, you have to always use the kernel config options stated and change this value.)
I hope this helps some people and takes a little stress off that 'TAB' key. 
Thanks.
