Is your phone fully paid for, or are you still under contract? If it's fully paid for, there is no reason for the service provider to refuse to unlock it. And it may in fact be illegal for them to refuse (it definitely should be illegal). If it's still under contract, you'll have to pay the early termination penalty. And then there will be no reason for them to refuse to unlock it.
Once it's unlocked, you can root it and install CyanogenMod on it. That's made using the AOSP (Android Open Source Project) builds that Google puts out. It's vanilla Android, with no carrier or handset bloatware. Unfortunately, that also means volunteers have to reverse-engineer any hardware-specific quirks to your particular handset to get it to...