>> 昼ご飯を 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. It works well if it's 昼ご飯を社食で食べたときに給仕さんに話してみます because it says 社食で implying you don't use the office cafeteria everyday. したらします can be also used in this case, but したときします is not used for things you are already up to now.