How new of a computer are you installing this on. X server probably wouldn't start due to lack of hardware support for your graphics card. Fedora 4 will most likely get you going.
I have never used Fedora but I did cut my teeth on Red Hat 9 while I was in school. Since then I have mainly used Ubuntu and SUSE. By far I like SUSE 10.0 because it is the most complete after installation. It allows you to load Java, flash, and many other video codecs while you install.
How much have you used Linux in the past. It is tricky to learn how to install new programs that aren't packages. I have some good sites that could help you learn some basics.
Ubuntu
Ubuntu Guide
SUSE
Tips for Linux
Adding Windows Media Support
Play around with those and let me know if they help any.