I have a Toshiba Tecra 800 running Windows ME.

I downloaded a 30 day free traial of McAfee Privacy Service.  After
the download I restarted the computer, per McAfee instructions.

Upon restart I got the opening Toshiba window, then the Windows MC
window, then a solid blue screen with a cursor that will move but
nothing else.  And the startup will go no further.

When I hit control-alt-delete, I get the Closs Program window (or as
some say the Program Manger window), and it shows nothing.  No
programs listed period.

After turning the laptop on and off several times, I decided to try a
safe mood boot up.

I then did a safe mode boot up, I got to the safe mode page, but it
would not go any further.

Any suggestions on what to do now?

"safe mode page" means windows did started, or just the logo screen
with the moving  bar before windows actually starts? If windows did
start in safe mode, click the start button, then settings, then
control panel. In the control panel window doubleclick "add/remove
programs". Select the offending McAfee software and click the
remove/uninstall button.

If windows didn't start at all either in safe or normal mode, press
the F8 button while the computer is starting to get the boot menu.
Select "Logged". Wait patiently, and after it crashes reboot again,
but this time select "

At the msdos prompt type "type c:\bootlog.txt". With some the name of
the problematic program or driver will be there. Type "ren
filename.something filename.bak" where filename is the problematic
file. Try to restart in normal mode again. Then uninstall the mcafee
software like above from the control panel. If things go wrong, reboot
to msdos prompt again and run "ren filename.bak filename.something".

Good luck!

Clarification...
After you type "type c:\bootlog.txt" look for the last line displayed.
Hopefully the end says something like
Dynamic init device xxx.vxd
Dynamic load device xxx.vxd
Dynamic init device yyy.vxd
Dynamic load device yyy.vxd
Dynamic init device zzz.vxd
---- end of file here---

Here zzz.vxd is the bad file. If there is no pathname given for the
file it is likely something like \windows\system, \windows\system32 or
\windows\system32\drivers.

If you are able to access Windows Safe Mode, ME offers a feature that
will allow you to "recall" your previous settings prior to installing
McAfee Privacy Manager.  This is available through Start -> Programs
-> Accessories -> System Tools.  I used the program to recall the
settings on my laptop after installing Norton AntiVirus which caused
problems similar to what you are describing.  I forget the exact name
of this application, and if you are unable to find it yourself, feel
free to ask me to look it up (I have Windows XP on the laptop now, but
I could obtain the name using several references I have available to
me).