求助，电话服务被公司擅自改成一年契约

我和妻子住在纽约州，以前一直使用本地一家电话公司frontier的固定电话服务，通话范围为本地。
今年二月，我因故让frontier将免费通话范围扩展到本州。我一共打了两次电话，第一次咨询价格变动，第二次正式要求变换服务。今年五月，我已经不再需要本州内通话，因此打电话让frontier将服务换回本地，却被告知州内通话是一年契约，如取消须交$200 cancel fee.
我非常震惊，因为两次电话中对方完全没有提到过一年契约的事，他们却一口咬定两次都告知我了。
今天由我妻子再次与他们argue,他们改口说正式给我开通（第二次）的客服确实没有告诉我一年契约的事，然而第一个客服却告知我了。当我妻子要求与那个客服对质时，他们说那个客服已经不在frontier工作了。
整个过程中我没有看见任何一年契约的条款，没有签过字，他们也没有任何证据证明他们确实告知了我。
现在他们把cancel fee降到了$100,却坚决不同意zero cancel fee.
钱虽然不多，但是我们无法忍受他们这种形同欺诈的行为。
我们已经向BBB(Best Business Bureau)投诉，但是不知道有没有用。
现在我们还想给他们写正式信件要求zero cancel fee，否则就提起诉讼。但有我们完全没有诉讼经验。
想请教各位网友几个问题:
除了提出法律诉讼的威胁外，不知道还有什么办法可以解决这件事？如果真要提起诉讼，是不是一定要请律师？是否可以到小额法庭提起诉讼？我们胜算大吗？如果败诉，我们是否需要付$200 还是 $100?
请多加指教，谢谢！