Sorry for the late follow up.
Honestly, your best bet would be to add entries to your sudoers file that allow your users to execute the commands required and not pass through sudosh for those commands.
Obviously, this only works if you know what commands they wish to run. Otherwise, you end up with arbitrary execution which is also fine if that's what you want.
Alternatively, Salt is certainly a practical solution to the issue but does suffer from the ability to audit commands run if you have multiple users executing in parallel (basically, you end up with an open root shell).
We actually include an MCollective module for this capability but I will freely admit that (at this time) MCO is not as user friendly.
I do think that the Choria updates that RI is working on are going to make a HUGE difference in usability.
We chose MCO both for the auditability of the platform as well as the ability to scale to large numbers of distributed hosts.