A combined "Wireless Router/ADSL Modem" from any of the mainstream providers - Netgear, Belkin, Linksys, D-Link etc - should be fine with any ADSL providers other than AOL.
<<< Are the router connections just to the phone line and power, or is there a lead from the router to the Base station pc? >>>
Normally, the initial configuration of a router requires a "wired" ethernet connection from one PC. Once configured though, that cable can be disconnected and all computers can connect wirelessly.
Personally, unless a computer is being used away from the router, I would always use a wired connection in preference to a wireless one - faster, more secure and more stable.