If you're going to stay with a central unit:
-Gas heating has historically been cheaper to operate. Consider installation costs, however. If you have a gas stub out in the air handler closet, this is the winner.
-Heat pumps are alright for heat. It's an AC run in reverse, so there is a pretty heavy electric drain.
-Resistive strips suck, period. Either go Gas heat, straight cool, or go heat pump.
As for brand... really they're all about the same. I had a Tempstar (Carrier) put in my house 5 years ago. It has had a couple of problems, but I found them to be acceptable due to the outstanding 10 year COMPLETE SYSTEM warranty. I find that unit to be fairly efficient (as AC units go). More important than the brand is the quality of the contractor doing the work. A great AC with a half-assed installation WILL have problems.
FWIW, a license is required for AC installation due to the refrigerant. There MAY also be requirements for a building permit.