Sorry no solution, but I have nearly the same issue. In my case it's definitely my S7 edge that is causing the delay of Pokemon spawning. I sometimes have a delay of up to two minutes when encountering Pokemon or I don't detect nearby Pokemon at all. I first tried logging in with a different Goolge+ account on my S7 edge but spawning of Pokemon was still delayed in relation to Iphone 5s, Z3 compact and Huawei P9 lite. All use the same mobile internetprovider.
After that test I transferred my mobile sim-card to the Z3 compact and haven't experienced any delay in relation to the other devices that I own or my friends own.
I hoped that the update of Pokemon Go that was released today would have fixed the issue so I tested my S7 edge again by transferring my mobile sim-card again from the Z3 compact tot de S7 edge. Same result on my S7 edge spawning of Pokemons is very often delayed in relation to the other devices :-\ While in the car (passenger-seat of-course) I don't detect Pokemons at all, while other passengers in the same car do.