If you send the degree symbol in the GSM alphabet input mode, you will see it correctly on your phone and keep your 160 chars, but the symbol will come through as gibberish or a ? for the one you're sending it to.
If you don't have a particular objection to just typing "degrees" in full, I'd say that would be the fastest and easiest solution.