I am looking for a recommendation for a distribution that will help me get a Samba server up and running with as little fuss as possible.

Thanks

I've done this on Debian and gentoo and am running Ubuntu on laptops.
I'd recommend Ubuntu or vanilla Debian.
The samba configuration was the tricky bit for me, but can be very straightforward.

It will depend a lot on the environment - if it's just for a small network, supporting the family windows boxes and it's behind a firewall, then it's a piece of cake (relatively).

Here's a very basic (and very insecure - but this may not be important) smb.conf

# Global parameters
[global]
workgroup = XXXXX
server string = File Store
security = SHARE
null passwords = Yes
guest account = guest
log file = /var/log/samba/log.%m
comment = Linux Samba Server
hosts allow = 192.168.0., 127.

[share]
comment = Shared files
path = /.../Share
read only = No
guest only = Yes
guest ok = Yes

Good luck.

I configured a server about 5 years ago and I seem to remember that some of the distros came with Samba included, and it just took a few steps to enable it while others required a seperate Samba installation. What catagory do Ubuntu and vanilla Debian fall in to?

Hmmm, good question.
I suspect that this is selectable at installation for both Debian and Ubuntu. I don't remember having to get samba separately when I set up the Debian box, but if there was a 'server' option, I would have chosen it.

On the Ubuntu laptop I'm on now, the server is not installed, but samba-common, which gives you client access to smb/windows shares, is on it. But I did a very hands-off install on the laptop, because I wanted to know what Ubuntu would be like on the 'do it all for me and don't ask me any questions' option. The answer was amazingly good (the only problem with this option was that the installation wiped my master boot record, without asking me first, which I had not wanted). But if I wanted to install the samba server on this I could do it in about 5 minutes (with a fast internet connection).