Kirk,
I'm running several vintages of Ubuntu now and for the last 3 years or so. I've tried a few others, including Red Hat, but that was back at 5.2 or so, ancient history in computer years. Fedora 3 and later should use RPM (Red Hat Package Manager) binary repositories. Ubuntu is built on Debian and uses .deb binary packages. Nearly any current linux you pick will have binary package management. Fedora is now at 10, so you might want to try it if you'd feel more at home there. Even software that isn't in official distribution repositories is often available in .rpm and .deb form on various web sites.
You should also be able to easily dual boot MS and linux if you have enough space on your hard drive, or a slot for another hard drive. I do that with a couple of machines here to keep other people in the family happy. I prefer to add a dedicated linux hard drive, and storage is pretty cheap now. Linux can also now read and write NTFS, and someone's done a program that allows MS Windows to read/write ext3 *nix formatted drives.
Lee