You should look carefully at the different ISPs before jumping in, as not all are created equal. Start with http://www.adslguide.org. Avoid anyone who wants you to sign up for a year, and (this is an opinion) anyone who insists on bundling a USB modem. Consider going with someone who offers fixed IP addresses; it doesn\'t have to cost more and you can plonk down a public server anytime you like. Go for a \'wires only\' service, though there is an advantage in getting the router from your ISP; they\'re more likely to talk to you when things go wrong (as they do).
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. D.