Thanks for the quick reply, I will try the Hardy Heron version as I have run that version in the past. I don't know when I will be able to install it but I will let you know how it works out.
Kubuntu, and Ubuntu are both for newer systems (IE, KDE and Gnome require a bit more resources), but using a desktop environment like XFCE, Fluxbox, or numerous others, they'll all run in older systems quite well.
Definitely ditch Win95. It would probably run like crap, and finding software for it that you could actually use (a better web browser, office suite, CD burning software, etc.) would likely be a huge pain.
I've run newer Linux distros on older machines, but mostly ex-Win98 systems. Usually of the P-III persuasion, and mainly running headless as servers for most of their life. Actually using it day to day for web-browsing and such would be something totally different. Using a machine as old as yours would definitely suck for doing half of the internet browsing most of us do, like Hulu, Youtube, Pandora, etc.