Phone quality varies greatly too, the "free" phones you get won't get as good as reception as a higher end model. I've tended to go higher end to get the better coverage, my last two phones have had much better reception than the cheapies I used to get.
You can also look at external antennas, most phones will have a small cover that can be removed to get to an antenna jack.