This wiki entry has a LOT of really good tips for making KDE look nice. For example making your K-menu's icons bigger (which I've ALWAYS wanted to do) and getting rid of the K-menu's ugly category headings can be achieved by editing ~/.kde/share/config/kickerrc and adding/modifying the [menus] entry:
[menus] MenuEntryHeight=32 ShowMenuTitles=false
After going into KControl, Desktop -> Panels -> Menus and turning off pretty much everything, my K-menu looks like the default Gnome menu:
There are options for changing the order of OK/Cancel buttons, changing the order things appear in your taskbar, etc. I also found disabling "archives as folders" in Konq's sidebar to be useful.