I've been using fedora for quite some time now, and while I don't find it lacking in any way I'm thinking of trying a new distro just for kicks. Are there any in particular I should consider, or avoid? I hear good things about Debian from my circle of friends, but it's a rather small circle of linux users in my area so I thought I would post the question to a broader community...

Debian:

Installation (Medium).
System configuration (Medium to hard).
Software package management (Easy).
Getting a system up and running fully -- Fairly Easy.
Config frontend tools to make your life easier -- no too many as FC but quite a few.

Slackware:

Installation (Medium to hard).
System configuration (Medium to hard).
Software package management (Medium).
Getting a system up and running fully -- Medium
Config tools to make your life easier -- very few. Must do manual configuration most times.

I did the same thing earlier this year. I kept Slack on one box and put Ubuntu (debian based) and SuSE on others. I'm enjoying the experience.

I can't say there are any to "avoid" in answer to your question..

I was in a car wreck December 26 2004 and suffered injuries from which I am still recovering and unable to work. Because of this I've had a LOT of time on my hands so I decided to check out a wide range of distros I'd never had time to check out before.
I've installed and used who knows how many in the past weeks and can say that over-all they all have some good and bad points.
SimplyMepis is my over-all favorite out-of-the-box distro because it has a very simple installation, excellent hardware detection,and is Debian based.
Gentoo is my personal favorite as I am an incurable 'tweaker'.
Debian is my second favorite.
What can I say? I'm a Linux junkie with a penguin on my back.
I'd say try as many as you have the time to check out and you'll likely find that 'just right' distro that fits your personality and needs.