Macbook pro mid 2012 slow down
Starting with OS X 10.9 it appears that OS X relies heavily on one having an SSD.  Since apps, which have been run once after startup, when relaunching them, they are mainly started off inactive memory/cache and therefore are faster the second time you start them.  This is in line with your statement that once they are loaded, they work fine.

As a comparison, in my Mac Pro (Early 2008), I used conventional HDDs for a very long time as well.  The computer originally came with Mac OS X 10.5 Leopard, which purred on this machine.  All following big cats also purred away without a problem at all.

However, with the naming convention change of OS X 10.9 Mavericks, loading something from the HDD became cumbersome along with it (tested with System Preferences which took 30(!) seconds to show up after the system was started).  Once started and closed, it re-opened fast (due to it still being in inactive memory or cache).

The same could be seen later with "Star Wars: The Old Republic" under Windows on the very same computer.  Using the HDD it took some time to load the game and/or planets.

While you can try things like clearing caches (which you can find at ~/Library/Caches), or back up all your data (e.g. using Time Machine) and reinstall OS X entirely (to verify that upgrading to newer OSs did not leave undesired settings), for the long haul I guess that you will not get around spending a bit more and get an SDD.  I did so myself eventually.

While dissatisfied to spend money as well, I am very satisfied with the results.

IMPORTANT: If you buy a non-Apple SSD drive, you want to check about trim to optimize it.  Otherwise you may wear it down too fast and spend even more money in buying a new one earlier.