Check out the threads here on mini-splits. I don't have one yet, but that is what I am planning on getting. They work much better at low temps than they used to.
I can give a testimonial to the mini-splits. I ended up ripping out my central furnace/air and went with Mini-Splits through the house. Compressor and all at the end of a 110F day uses less energy than the blower motor alone of the old AC.

Not to mention I regained two attics worth of storage, and a storage closet and a half inside the house, and was able to raise one short ceiling as a result of getting rid of all the space sucking ductwork and inside furnace. Still haven't gotten around to installing one in the garage, but it is coming... It used to be kinda avante garde in the US, but Home Depot sells the Mitsubishi's now.
For heat, I had no issues with heat with it being 5F outside this last winter.