Many stores carry unlocked phones, but the locking of phones and the discount are specifically linked. You can buy an unlocked, unsubsidized phone from any carrier, but if you buy it on contract, it will likely be locked.

Not entirely sure this applies across ALL carriers, but it does apply to ATT/Sprint/TMO I believe.