>> 昼ご飯を a.食べた時 b.食べたら、すぐ出かけます。  

> Is it perhaps the すぐ that made it that way?

I think you are right. The two words are connected each other very well as ～したらすぐ to us.  

したときします has a notion that you are just waiting for that occasion. We don't use this expression for things we are up to now.  

It works if it's 昼ご飯を社食で食べたときに（給仕さんに話してみます, etc.) because it says 社食で, and we say this when we don't really know when we eat at the office cafeteria.