I'm not sure how good FIDO's cutomer service is, but with the carriers I've dealt with, there is usually some sort of warranty, so if your new phone doesn't pick up a signal well enough, it usually warrants a replacement or a fair exchange where you pay the difference on a more expensive replacement.
I checked out FIDO's lineup. They actually have some OK deals, the drawback is that you have to get a 3 year contract to get the best deals and they have marginal deals for the 2 year.
http://www.fido.ca/portal/product/product.do?sort=price&filter=
If you are going to get a phone with no contract, you may want to shop around for a basic unlocked phone because it might actually be cheaper than going through your provider.