Ok guys, I'm pretty sure I found the culprit, and I think it was a virus.

I spent a good amount of time in Activity Monitor trying to see if anything was taking up too many resources. They use Chrome which I know is pretty notorious for memory leaks on OSX (and Windows sometimes), but while the Mac seemed to be maxing out its physical RAM, the pressure was still well in the green (this was Mavericks).

So while I was doing other things like working on the Time Machine issue (turned out to be super simple, it was pointing at a device that wasn't there anymore), I suddenly noticed an entry at the top of the memory usage list, and it started sucking up memory. Within about 20 seconds the memory pressure was pegged at the maximum, which this entry called "appOS" was running out of control and the whole computer started seizing. A quick search led me to believe that the computer was infected, making it the first Mac I've come across that had a virus (I know it's not novel, but I don't work on a lot of Macs).

I was able to clean it off and get it running perfectly smoothly again.

Thanks for the advice, though. I'll use it going forward. Unfortunately, on this particular model, which ended up being a late 2013 iMac 21.5", the general consensus on the web was that these are a nightmare for memory upgrades, so I wasn't about to touch that. I'd rather not do an SSD either.