Recommendations for low-powered home PC running Linux desktop

I am looking to dive into the Linux desktop world, which is to say that I've
never played with Linux before.  With that in mind...

I've got a couple of 266MHz Pentiums gathering desk, and would like to play
with a desktop Linux.  I can probably get one of the pc's to 512MB of RAM.

I've tried Ubuntu, but for some reason is stuck in 640x480 display mode
(that's the only choice given).  I understand that video drivers can be hit
& miss with some Linux distros.  But it is also very slow with 256MB of
RAM.  I have been unable to find any hardware requirements/recommendations
for Ubuntu that specify a recommended processor level.

I checked out OSDir.com, found some other distros.  Freespire, a freebie
from Linspire/Lindows, recommends a 800MHz or better CPU.   Guess I won't be
trying that one.

I've heard that Windows users are more comfortable with the KDE environment
than the GNOME environment.  Any opinions on that?

TIA,
Dan