I have an original Surface - pre-ordered and received on launch day. I did start having problems that sounded somewhat like you're describing back on 8.0 during the spring of last year: horrible lagging, freezing, needing to shut down with the power button, etc. It got so bad I was convinced there was a hardware problem, but I decided to try a refresh first. Actually, I couldn't get the system to do a refresh, and it was becoming so unstable that I just decided to do a scorched earth reset. After that, it seemed to be working OK, and since I had blown everything away and was starting fresh anyway, I went ahead and put the 8.1 preview on it. Ever since, it's been working well up to and including today on 8.1 RTM. It's never been a speed demon, and it does get a little laggy at times, particularly in metro IE, but never freezes or has any significant delays in operation. (And I've got 2 other accounts on it for my sons, though to be honest, they don't use it much.) Plus I have 61 Metro app tiles pinned to my start screen as well as some additional IE shortcuts and the Office app tiles.
As a second data point, I picked up one of the cheap refurb units off eBay for my mother and set it up for her, with accounts for both of us so I could handle running all the updates and the 8.1 upgrade. It's running just as smoothly as mine.
Now I realize you've done refreshes, resets, and got a replacement device, so obviously whatever had happened to my Surface last spring isn't relevant to your situation. However, it's interesting to me that what should be essentially identical devices should be acting so very differently. Since none of the other suggestions seem to be helping, I'll throw out some that may be a little off the wall, but might not be entirely useless. I've numbered these to separate them, but they're not in any particular order.
1. You mentioned that you thought the slowdowns didn't occur until after you added multiple accounts. Does the system seem slow if only one account is logged in? In other words, does just having another account make your surface run slow or does another account have to be logged in at the same time? Does deleting the other account(s) make the problem go away?
2. Have you checked memory usage in Resource Monitor? When the Surface is acting slow, is there free physical memory? Some of the problems you describe sound like what can happen in Windows if it starts swapping heavily.
3. Is your Surface always connected to a particular wifi network, like your home network? If so, can you try connecting to a different network? (A neighbor's wifi, or someplace with free wifi?) I've seen cases where a router starts having subtle problems due to being in the initial stages of failure or just going dumb and needing a reboot. However, most devices will still connect OK, but one will be a canary in the coal mine and suffer drop outs or slow speeds long before the others. In particular this happened to me with an older cheapy laptop at home that started having abysmal network performance with its built-in wifi. As a test I plugged a USB wifi dongle in and that worked fine. I figured the built in network adapter was dead, but it wasn't worth trying to fix it. A few weeks later, however, nothing could connect to the wifi network. After replacing my router, everything worked again, including the laptop.
4. Do you have an SD card installed? Are you doing anything hacky with it, like the old 8.0 workarounds for the libraries, or some of the hacks for moving user accounts? If so, can you undo those and see if the problems go away? Even if you're not doing anything non-standard with it, have you tried removing it to see if that would help? (I have seen other device wonkiness tied to problems with SD cards.)
5. Have you tried running any benchmark utilities just to see if there's something obviously wrong in terms of performance? I'm thinking something like PC Benchmark for the Surface hardware or Network Speed Test for your network performance. Just something to maybe help narrow down where the problem could be.