For the 6360? I recommend Debian. Ubuntu has too much overhead. Do a base installation and then install Xorg and <insert-favorite-DE-here>. I did that on a Compaq Presario that was comprised of an AMD K6-300, 64 MB RAM, 4 GB hard drive, and S3 Virge video. Did a basic installation of Debian Etch and then installed Xorg, XFCE, and some other apps. I was quite surprised at how usable this meager system was, although browsing "Web 2.0" sites did bring the machine to a bit of a crawl. But for general use it was quite usable.
Consider also that since this Mac is considered an "Old World" Mac, you'll need to have a small Mac OS partition somewhere and use BootX as the bootloader to Debian. You'll also need it during installation. It's not as trivial as installing it on a "New World" Mac, but it's definitely a fun process. Best place to check for installing Linux/ppc is the following site:
http://www.penguinppc.org
I installed Debian Sarge (the previous version of Debian, 3.x) on an old Motorola StarMax 4000 Macintosh clone and it ran wonderfully on it. I even installed Ubuntu 5.04 once on it but it was too much for the StarMax to handle compared to Sarge.
You could also try one of the BSDs. NetBSD runs on practically anything. There is also a FreeBSD for PowerPC, but I don't know that it supports "Old World" Macs.