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

Also I find we say したらします or したらすぐします for things we have already made up mind to do.  

したときします is 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.