I don't remember the earliest version I used, but I vividly remember kde 3.5 and 4 because the transition was really rough. Major regressions and highly disruptive at first, but it laid the groundwork for modern kde and haven't had anything like that since. I jumped ship to gnome out of spite but was back to kde in short order.
My earliest memories with KDE was how I was not able to install it because with RedHat 5.0 you needed to download the source code and all the libraries and build it all by yourself.
I asked in the Linux IRC channel some help, gave my root account to a helpful user and very quickly learned about computer security.