The Ubuntu Live CD will bog down in less than 256MB ram. What you want is the Ubuntu alternate installer CD. That will run a conventional install, and should work fine in 128MB RAM.
You'll probably want a bigger hard disk.
If so, any recommendations on a laptop friendly Linux flavor
Debian.
(Edited to add)
Ubuntu is essentially Debian, with a user security model much like OSX's (no root user, admin users sudo for admin tasks). I've got Debian working just fine, with almost zero tweaking needed (Gnome power tools don't work quite right on this, but kpowersave (part of KDE) does), on a Compaq Armada of probably about the same vintage as your Gateway.
Don't install Debian stable aka "sarge". If and only if you have a high speed connection to the Internet, you want to install from the Debian etch net install CD. The iso for that is about 130MB.
Gnome will run "OK", sort of, in 128MB. 256 will be much better. There are a bunch of lightweight window managers out there. XFCE is good. I also like WindowMaker.
I still think you should get a bigger disk.