How hard is it to do? I'm not a noob at computer things, but I'm a noob at Linux, so any help or suggestions will be greatly appreciated.
AIM me if you decide to go Kubuntu. I'll walk you through the install process
Depending on your distro, you could just let it run set-up.
If you are going to use an Ubuntu based distro, then you could set it up with Wubi, and you wouldnt even have to format or partition anything.