Great question. I would say the difference between the two is: "Put up with" is more like an unavoidable annoyance that you can ignore to some degree. E.g. I'm going to the park, where I will have to put up with noisy children playing. If 'deal with' was used here, it could imply that you might intervene to silence the children (but not necessarily). "Deal with" is more directly having to put oneself through something. E.g. I have to buy a TV so when I go into the store I will have to deal with the annoying sales people. If 'put up with' was used here, it would imply that you don't need to negotiate a sale with them and you can just ignore them (sometimes the case!). There are sentences where one would use 'deal with' but where 'put up with' would not convey the same meaning. Such as where one would "Have to go deal with this problem." would mean to resolve it. E.g. "I'm going to deal with the leaking roof issue" would mean that one would be mending the roof. Whereas "I'm going to put up with the leaking roof issue" would mean that the leaky roof would be ignored or temporary measures put in place such as buckets to catch dripping water.

Putting up with someone is like tolerating them. Dealing with someone can mean resolving some sort of conflict with or involving that person, or keeping that person in line, or out of trouble.