Not one person I know who bought an iphone4 kept it, they all returned them for poor service which is at&ts fault, but certainly not worth the monthly cost. I also heard that even though it was a great phone, it still had stupid faults that apple should have never put out, besides the antenna problem.
I have an HTC hero now and its great. If HTC doesn't come out with any new phones by the end of next year when my 2 year contract is up and I get $120 towards a new phone for signing up again, I will definitely go with the htc evo 4g. I've heard nothing but great things.
As far as service, I have sprint and won't change if I can help it. Sprint has had a bad rap in the past, but they have really changed. I have dropped a call once with this hero, no bs. I get 3g internet coverage (this is a 3g phone) pretty much everywhere (even out at the farm, 10 miles from a highway)
I had full service with 3g to and from michigan this summer on the back highways, a buddy that had an iphone 4 (he returned it) had no service to and from, or while we were there. We were several miles from towers so mine wasn't great, but it was there.
I'd consider sprint and anything made by htc