KDE / Ubuntu / XFCE / whatever - take your pick, it's really just down to preference. KDE is a bit more fancy these days but the old, plain and simple Gnome does it for me without an issue
As for installing it on a laptop - laptop support is a lot better these days but bear in mind it's not perfect at all, you might be better putting it on a PC first, getting some experience with using it and then putting it on your laptop when you're a bit more confident with dealing with problems. Course you might not have any, but if you do having some experience is always useful.
In terms of distributions - Ubuntu or SUSE would be good choices if you're relatively new to Linux in general. I've found Ubuntu tends to be a bit better than SUSE about setting most hardware up for you - SUSE used to have the edge graphically but Ubuntu has probably caught up now. Either should work though, they're both good distros. SUSE is a bit more flexible as well, you can choose whether to install KDE / Gnome / another environment from within the same install process rather than be pointed at a different distribution for a different OS. Suse is also very good in the sense that you barely need to reboot, even when switching kernels (most of the time anyway!)
Good luck with it