is always a good idea ;)
There are a bucket load of choices for ISP, the best option for you depends on how you use the internet.
click here for a pretty good decision-guide.
AOL can't prevent you leaving. Because you don't want an uninterrupted service you can simply notify them that you intend to terminate your contract with them, then start afresh with a new ISP when you have your new phone line (otherwise you would need a migration code from them).