I think nearly all ISPs want Direct debit these days.
What's wrong with it anyway? It's a darn sight safer than a Continuous Charge Authority on a credit card as you have no control over that, but a lot of control over d/ds.
Unless you mean you paid each bill individually yourself using the credit card.
Re a new ISP, you have a hundred or so to choose from, most of them better than the TalkTalk (non-LLU) service you are currently on. BT broadband is amongst the worst. The important questions before we can narrow that down to two or three for you are:-
Excluding the phone line cost, how much are you paying for broadband at the moment, would you find cheaper very desirable, or would you pay more for a top-notch service?
Have you any idea how much you download and upload per month? That makes a huge difference to costs. Did your F2S service and now your TT one have an allowance, and is it enough?
Do you do a lot of gaming, or P2P downloading etc.?
Who provides your email service? F2S/TT, or gmail or what?
Can you try to find and post your line stats from your modem/router please? See here