The most noticeable change in KDE4 is the visual appearance and the desktop interface. The old interface has been replaced by Plasma, which incorporates new visual elements to make things prettier. Other features like compositing and hardware acceleration help make it smoother as well. The default themes and window decorations coming with Plasma look a lot smoother than the stock ones in 3.5 as well (at least in my eyes).
KDE4 also brings technical improvements, such as overhauled libraries and being built upon QT4. If you are a KDE user, it's definitely worth taking a look.