Playing again and this idea came to me. Remove stealth Cones and suddenly stealth would be much more Stealth skill based. I think a big part of the issue with stealth is simply that you can see where the enemy cones are. So, you can more easily avoid walking into the cones.
You wouldn't be able to exploit the stealth mechanics as well if you couldn't see the cones. It would then just be a matter of you, the player, trying to time sneaking past while their back is turned, like in Zelda games and such. I think this simple change could really make all the difference.
Oh, and make it so armor actually gives disadvantage. I'd it does already, it sure doesn't seem like it.
