Maybe this isn't the answer you wanted to hear, and maybe also it's my paranoia about RAM (I made sure my new rMBP maxed out at 16 GB, particularly because RAM is now soldered to the motherboard), but the fact is that it's the cheapest upgrade possible on your computer. When you don't have enough RAM, the performance hit you take, when the computer starts paging to the hard drive, is simply monstrous.
Honestly I think 4 GB of RAM, today, is on the low side. Only the lowest end Macs currently for sale feature 4 GB of RAM, and some come with 16 GB standard. Mavericks has a compressed memory feature that should supposedly help with RAM pressure, but there's only so much that can be done. Your computer can certainly use 8 GB of RAM and most likely 16 GB of RAM, as reported here. I just checked Newegg and you can get 2 x 4GB RAM modules (for a total of 8 GB) of RAM for about $70 and 2 x 8GB for about $140 (reputable brands in both cases).
Then there's the possibility of replacing your hard drive with an SSD, but that's a much more expensive upgrade, and RAM should help a lot already. If you plan on staying with this computer for a long time, it's a possibility you definitely should consider since it breathes new life into any computer with a mechanical HDD. Also, prices are constantly falling, so if a RAM upgrade helps you now, you can hold out for a bit and get a good deal on an SSD later.
If it helps you somehow, I can happily report my previous computer, a mid-2010 15" MBP with 8 GB of RAM and a 300 GB SSD, absolutely flies with Mavericks installed, and I consider myself a fairly heavy user, including Parallels running most of the time. Most apps opened within a single Dock bounce. My wife needed a better computer and I needed more disk space (my average free space on the last few months was 10 GB or so), so I ended up ordering a retina MBP. But I can assure you that, other than the disk space problem, I could easily keep using that computer for another couple of years, it was just that fast.