Here is the whole story:

My computer came with WinME installed. I installed red Hat 7.2 (my first linux distro) on the last few gigs of my HD. I used grub to multiboot. There were some things I did not like about it, so I started considering trying other distros. Then one day I defragged my Win partition. The next time I booted, grub did not work. Its been a while, so I do not remember entirely, but I think it threw up a command prompt that did nothing.

So I installed Mandrake 8.1, expecting LILO to overwrite grub. No such luck: no more command prompt, just the word GRUB printed in the top left corner of an otherwise blank screen. Mandrake still worked with a boot disk though. Then I got a boot disk for windows and did "fdisk /mbr". Now when I try to boot I just the message no operating system present.

Anybody got any suggestions?

Also, before I was accessing the internet via network. Now I nead to do it via cable modem (still going through my NIC card) but it does not work. It just hangs when I reach the initializing eth0 line of startup (or whatever). I know I can bypass this, but I nead the internet with Linux.

Install lilo in the MBR and you should be fine..

As for the Internet, its 'ok. Takes me a long time too =)
You can just press ctrl+c and then (as root) do pump, to save time.

I tried installing Lilo using the rpm with the line rpm -ivh lilo...rpm, and that did not fix it. Is there something else I need to do?

I recently (like yesterday) did my first kernel upgrade. I followed all the instructions and did a good job. All the way up until I tried to to boot into it. It wouldn't boot. So I read the instructions again and it said /sbin/lilo So I did that and it did something in lilo. But now I can boot into my new kernel. So maybe that's what you need to do. run /sbin/lilo in a Console.

Yes, you also need to set up your /etc/lilo.conf file in Mandrake, or whatever you want. Then you need to run lilo (as root). Then, the boot loader should install itself into mbr.
You did fdisk /mbr. This erazed all the contents from the bootsector from the HD and that's why it can't find an operating system. Once you have lilo or grub installed, it should work fine.

What you did was to install the Lilo software, which is the first step. Then you must actually RUN Lilo to set the correct instructions onto the MBR. Just follow Config's instructions, and Lilo should be in charge of your boot in no time .

I did that, but it still says the OS is missing.

BTW, the eth0 thing did finish when I gave it enough time, but it took about 3 minutes, which means that by itself it would just about double my boot time if I was not using a boot disk. Is there any way to speed it up? Will it be faster when I am not using a boot disk?

give us the contents of how your drive is laid out, we might be able to help with the lilo.conf file.
cat /etc/fstab

And the no operating system found problem. Is windows still loaded? Have you tried looking at your windows partition info using a windows boot disk and running fdisk just to view the info?

Its my Fat partition, then boot, then swap, then / partitions. Windows is definitely still there. I am really confused because for some reason Lilo is not writing to my MBR, which means it should not matter what is going on with the rest of the disk.

Post a copy of your /etc/lilo.conf file and the output of this command
fdisk -l /dev/hda