I have the same or similar MBP as you, late 2011. I had the 750GB 5400RPM HDD. It came with Lion, which I updated to ML and then Mavericks via MAS.
It started to get slow, beach balls, etc. I'd log in and watch icons bounce 10-20x before apps would launch. However, my boot times, beach ball frequency and issues didn't seem as bad as yours. BTW, I had 8GB from the start, so I can't compare 4 to 8GB of ram.
I fixed my issue by buying a SSD and installing Mavericks clean.
No more beach balls, no more slowdowns. It works better than the day I brought it home.
It's not the best solution for everyone, but it fixed my issues.
Thanks for the report! I see the genius tomorrow.
A reminder this follows a clean install of Mavericks, after which the computer seemed to function ok for about 3 days. Have run Disk Utility from recover mode. Repaired HD, message was "normal".
Checked Permissions, message was "normal". Also upgraded to 8GB RAM and that registers in "about this Mac". And BTW, this is something that has been deteriorating over a period of a couple of months, steadily getting worse. At one point it was just an annoyance with a few SBs now and then, now they have reached such a state that the computer is unusable. I'm suspecting I'll be very glad I paid for the extended warranty, which ime pays off about 60-70% of the time.
Here is how bad it is:
Restarted last night due to "glacial" issue- normal restart allowed it to do it's thing and shut down naturally (not forced).
2316- Selected Restart
2327- Gray screen appeared
2330- Startup tone
2332- Login page, logged in
2342- Functional desktop
27 minutes
Used Safari- left it running. Put to sleep last night
This morning woke up
0741- woke up
0742- things look normal. Launch App Store
0743-45 App Store icon bounces
0746- App store window appears
0746-59- SBs (spinning balls)
0759- unplug external USB hub and external HDs. They had not appeared on the desktop anyway.
0804-16 Desktop frozen and unresponsive
35 minutes
Yelled "BS!" and selected force Restart
0816- Force Restart
0818- Login Window, logged in.
0820- blank App Store Window appeared
0824-49- SBs
0850- Able to quit App Store
0852- Safari window appears, but it's frozen.
0902- Safari momentarily seems functional but then...
0903-15 SBs
59 minutes
In disgust, put to sleep in anticipation of Genius bar, started using my PC which starts and achieves a funtional desktop in about 20 sec.
Anyone think it would be better to carry this to the Genius Bar asleep in it's problem state or completely shut down? 
Thanks!