>> 昼ご飯を 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.  

したときします doesn't have the notion that you already made up mind to do the thing. It's used when we are just waiting for that occasion. 昼ご飯を食べたときに could sound as though you don't eat lunch everyday. It might work if it's 昼ご飯を社食で食べたときに給仕さんに話してみます because it says 社食で implying you don't use the office cafeteria everyday.