It seems you are looking in the right places. From what you say, I'd suggest pulling the IAC out and cleaning it with carb cleaner. I say this because it may have some sticky deposits in it and these could set up when cold. After the first 'loosening' action, the IAC would be ok until the next time it sits and cools.

If that doesn't fix the problem, then I'd clean the throttle body and linkage and check the throttle switch for proper action at idle. I like to both listen for the switch clicking when the throttle reaches idle position and also use an ohmmeter to be sure the contacts are working. If the switch was a little out of adjustment or the throttle and/or linkage was sticking and not letting the throttle plate go to idle position until things had moved or warmed up, you could get your problem.