Saying that somebody can just take the next flight is not a solution. For
either person, the one with a service dog or the one allergic, that flight
may be the necessary one to meet connections for business purposes and
taking another simply won't work.
I think the airline should, given such a situation, place one person at the front and one at the back of the plane to keep them as far apart as possible. Such problems are tricky and it can be a c hallenge to meet everyone's needs and rights.