If I recall, KDE seemed odd because it was developed by a commercial entity. Gnome was developed by individual _hackers_. Funny, though, since RH was commercializing Linux at the time. I was happy to buy the box since downloading over dial up seemed impossible.
I'm sure my history is off, but KDE is a good memory.
My favorite memory from that era was the bumper sticker I got at the Raleigh Linux convention:
"In a world without fences, who needs Gates?"