Is the check engine light on, is it throwing any codes?

This is a long shot, but it's the only theory I could come up with...

As I understand it, the A/C idle up system works by allowing more air into the intake at idle. The only way I could see this smoothing things out is if the truck were running rich, i.e. leaking injector maybe? Can't think of a single other thing that would cause that.

May want to go through and make sure the valve adjustments are good too, although the fact that you can make it run fine with the A/C makes me doubt the problem lies there.