I'm having this exact same problem right now. let me tell you what i've discovered so far, these steps (that failed for me) may work for you.
if you are using grub, read the configuration files (man grub) and look for something like what i'm going to describe below for lilo. grub can do the same thing i just don't know exactly how.
If you are using lilo as your boot loader, just change a line in the /etc/lilo.conf file.
somewhere near the top there should be a line that says
vga=normal
or maybe `vga=extended'
change that to
vga=ask
and on boot up you will be presented with a list of modes your video supports, shown as column by row. pick the one with the biggest number, or enter `scan'. the number you pick can be inserted into the lilo.conf file easily (so you won't be prompted each time)
vga=6
or whatever number you liked best

if you pick an invalid mode, you probably won't be able to read anything while it boots up. thats ok, just wait until you are certain its finished, then log in carefully (without typos since you can't see) and immediately reboot.
if this steps above don't work for you, for a reason such as all the modes presented by vga=ask are still super huge, then you may need to compile your kernel with more console support. This is happening to me right now

I've just compiled the 2.4.21 kernel and the most columns and rows i can squeeze out of it are 80 and 30 respectively. This is not enough!! if X windows can display itty bitty letters in 1024x768 then why can't i get 120 columns out of my console?
anybody with advice on how to make the console font smaller, please share your wisdom (*bow*)
-modnar