W95-98-98se-Me: no security at all, because good firewalls (and antivirus) don't run on them any more. I use these Win for offline computers.
95 is MUCH faster than Me which is perceivably faster and better than 98-98se. All cost just the postage at eBay, so prefer Me to 95 if you have at least 64MB and 200MHz.
Experimentally, Xp and applications on it start faster than W2k thanks to the prefetch, so prefer Xp if you have 512MB. W2k runs at full speed on 256MB and loses just 10% on 128MB.
About 95-98-98se-Me (Me is not 2000), I agree drivers are harder to find. Nearly impossible to run Usb on W95. And W95 (as well as Nt4) is a lot more difficult to install than Xp.
So Me could be an option IF your applications run on it, 95 might be possible if you find applications for it and you're willing to learn installing it and looking for drivers... Or stay with Xp!
My only experience with Ubuntu is with the desktop edition, it is significantly slower than W2k which is slower than Xp on 512MB. But if the notebook edition is lighter, fine! Truly easy to install.
Tuning the software installation improves a computer a lot. Removing Acrobat Reader and Open Office (or at least their so-called "quick launchers") accelerates Windows startup quite a bit. Remove any firewall and permanent antivirus if you don't surf. Make a massacre with MsConfig. Choosing quick applications also makes more difference than big hardware.
Did you consider replacing your hard disk? This is the huge weak point of any notebook. Changing from 5400/min to 7200/min, if possible with more GB per platter, makes a huge difference. A Flash disk would also be good - somewhat better than a 7200/min 2.5" disk, and comparable with a 7200/min 3.5" disk. Some people use a CF flashcard instead of an SSD: cheaper, but speed isn't guaranteed in neither case - it needs a precise investigation.
I know a computer with a 1400MHz PIII and 512MB but a good disk (7k160 or J8160), it boots in 28s and is very responsive thereafter. An Atom shouldn't be worse.