From: me@davidfairey.org.uk [mailto:me@davidfairey.org.uk]
I would suggest Andrews&Arnold (www.aaisp.net) for they do support Linux users and supply a number of fixed IP addresses free of charge. Although they are more expensive. They also sell routers which AFAIK come automatically configured for your connection.
They also charge a fairly hefty connection fee but the good sides are they made BT fix our phone line that was not suitable for ADSL (BT said we could never have adsl as we were too far from the exchange and other lies), replied to my one and only tech query in record time (i.e. out of hours!) and setup the reverse DNS I asked for about 2 minutes afterwards, gave me an ipv6 connection along with the ipv4, got us online in 3 days (from initial order to connection!), support linux (and any OS you like if it has an tcp/ip stack and can connect to adsl then they will endeavor to help you out), they also gave us a useful setup book with all of our connection details in which will be most useful when something goes wrong and we can't remember our password or server names or something.
In all, I can't fault them. This is definetly a case of "you get what you pay for" I will definetly be buying adsl connection services from them in the future.
Adam