Eh, I have Sprint. When I look at my phone connection I could have 4G, 3G, or LTE at any given moment.
The very basic principle of the game requires that you have internet and GPS connection at all times. As long as you can get the proper GPS going, you should be fine. If the game accurately follows you about as you travel to any place, that is a good sign. The game should work fine for you.
The leaf patches show you where pokemon most often show up. AKA, they show up more often than at other places. They will throw up leaves even when a pokemon is not there but you should still check them on a regular basis.
As 5hift mentioned, the in game radar is completely broken. Even if it weren't.... pokevision.com would be the answer for you. it shows you where pokemon have spawned and for how long they are supposed to be there. Godot and I have tested this site enough to know that
A: the in-app radar is absolute. Close the program and reopen it to be sure. If it doesn't show up, even as broken as it is, it doesn't show up again, it either isn't there or you've already gotten your chance at it.
B. The site is usually accurate, but the actual appearance of a mon could be several meters to the north.If there are any other pokemon in that area according to the site, evaluate the displacement and move accordingly. You will likely find it.
C. If you think you know exactly where a pokemon is... zoom in to max and you will likely find it in a different area if you didn't zoom to max in the first place. Not fully zoomed in areas can put you too far or not far enough to find what you are after.
D. pokevision is a tool. As the common army saying goes, be smarter than the tool you work with. Know the times it could be accurate or inaccurate and adjust accordingly.
E. sometimes, but not often, the time a pokemon shows up on pokevision is on a lag and shows up on the site long after it shows up on your in-game radar. As mentioned above, the in-game radar is always right. This time you have to work with your fellow trainers to find exactly where this mon is.
F. Most people don't care what team you are on. They will ask you what team you are on and be like 'ya' if you are on the same team. But 99.9% of the time they will lead you to the right direction of the mon you are looking for. Most things transcend team alignment.
tl:dr- as long as you have a good enough provider to get you accurate gps as you walk, you will be able to enjoy this game. Not that many places have pokemon showing up all the time. So it may not necessarily be your service quality but the time and location of your walking.