All I know is what you said:
Regardless, you obviously know what you are doing.

Maybe this helps for finding good distribution that will suite your needs. As I worked with all of the above mentioned and also with RedHat/Centos.

If you need a distro that just does what it should go with slackware or debian. For sure slackware has some learning curve but afterwards you are able to administrate nearly every *nix like system.
I'm not using slackware anymore so can't say about the package managment but I'll guess it can compete with the one of debian.
Debian is a bit more tweaked *nix than slack and might be a bit easier to adopt. As I'm working with debian right now I'd choose it. Specialy cause there is a nice feature of automated installation of clients and servers. http://wiki.debian.org/FAI. Also it's a one shot to get a central repository so clients can be easily updated.

When it comes to SuSE I can only say that it got as much to do with *nix as a Tree has with the sea. In my opionion its made for the Windows used mouse clickers. And I did not had a good time with this lady. It just sometimes refuses to do what I thought it would.

RedHat costs money so might not be an option for you. Rather go with CentOS which is a free redhat derivate.
Both are nice and clean distributions.

Maybe you should install all of them on a machine and see what you like and have a flavor for.
All of those come with a more or less GUI installer.

My own personal preference would be for SuSE for the desktops. If you retain your active directory for a time, the dialog to configure logons looks pretty slick. SE-Linux wouldn't be a problem for servers. Only authorized people would touch a server and be trained to deal with it.

Google for "IBM Red Book Linux Migration". I remember they had publications that outlined the steps in Migrating. You do need to plan ahead.

A guest on the TLLTS podcast was involved in migrating his school district to Linux. They didn't prepare the teachers who came back in the fall to find Windows was gone. He recommended preparing the users for the change ahead of time. There were protests at first but they adjusted in time.

One idea is to change to Firefox, OpenOffice an email client such as Thunderbird while still using Windows. This will familiarize users with the same programs they would be running in Linux.