Tinc looks interesting, I will test that as well.
Considering the huge difference in context switches and interrupts, I don't think that encryption induced CPU load is the only issue here.
Kernel stuff on its own doesn't just magically run faster, of course. But in this case, I think it's the constant interaction between user-space and kernel-space, which causes the problem. That's an issue that will impact any user-space solution to a networking problem.
Can 1200 extra context switches and ~6400 extra interrupts per second use up 100% cpu? In fact you mention that for stunnel most of the CPU was in userspace and not the kernel which would indicate time spent actually using the CPU instead of doing context-switches and interrupts, which I assume top would show as "sys".
I also find the extra interrupts strange. I wonder if vCider is sending bigger packets and what caching/latency implications that might have.
stunnel tries to compress traffic as well, which works if you send a lot of stuff that isn't already compressed. But most of what's sent these days (multi-media?) already is encrypted, so this will be a wasted effort.
tinc (http://tinc-vpn.org/) would seem like a more interesting comparable than stunnel since it sets up a p2p VPN that routes all IP traffic instead of just a point-to-point link.