Does anyone have any ideas on the best distro to run a media server? I have a box here that I want to put our MP3's and stuff on, so it'll run through the whole network.

So A) Is Fedora Core, or Ubuntu, or whatever else just as good for it as any other, and

B) Is there a way to do it without an XWindows? Like, if I just open a network on one of my computers, to just drop it right into the folder, like you would if it were just on your computer?

I'm not sure what all more information you'd need.. So i'll keep checking back.

The box will be a Celeron, 633MHz. Lots of RAM and lots of HD space.

I won't pretend to be an expert, but here's what I know:

Any distro will do or can be made to do what you want. To make life easier, look for a distro that has Samba and NFS servers on it, most do. You might also want some version of Apache as well. All of these will run just fine without X.
Now a shameless plug. Take a look at SLAMPP. Reasonable install footprint, it doesn't try to be anything other than a server, and it has a simple browser-based config system, so you should be able to get up and running quickly. I like it, anyway.

Have a look at Debian or Gentoo.
You can install these without GUI's and the other clutter, and there is plenty of documentation on the internet.
As somnium says look for Samba, this will make it easier for you to share with windows.

The above is good advice, you'll want Samba (Windows) or NFS (POSIX) or both.

You dont need X running, i had a Debian music server running console only, you can use samba to move the files around locally from a work station, or setup SSH and login via that, i also played mine off of the server, instead of locally, so i setup Cplay, which is an excellent CLI music player. Just SSH in, cplay <folder> or <playlist> (.pls or .meu cant remember) and off it went.

Personally i'd go with Arch or Debian, both very nice and stable, with access to alot of packages (you'll need codecs/enginers for your players etc.