Yes, an unlocked phone would be better, but unless you're going to do an illegal one, you might have to wait until the end of the contract. At least that's what ATT told me.
Not necessarily. You can device swap a new iPhone with a 5s in the middle of the contract and at&t will be happy to unlock the offed 5s after 14 days (the return period of the new iPhone).