We've got Pipex DSL here at Jen's flat. They're not the cheapest, but I've had absolutely no problem with them (except when BT have tripped over something and brought down the whole of South East England).

As for a modem: as others have said, get a combined DSL modem and router. It'll do the firewalling and NAT stuff you'll need to get multiple computers connected.

I've got a D-Link DSL604+ doing that here. You just plug it into the phone line (with a microfilter), and plug the computers into the back[1]. It's also got built-in wireless, which works really well with my laptop.

As for speed, as others have said, you'll generally expect the full 512Kbps.

On the Mac OS X thing, Freeserve probably don't support it for two reasons:
1. Support costs. They'd have to train their people on something other than Windows. They probably don't support Linux either.
2. Their USB cable modem doesn't work with it.

Get a router. It'll make your life much easier than trying to route via the PC.

[1] Mine drops down to a sequence of hubs and switches to get from where the router is to where the PCs are. I must get hold of some longer bits of cable.