Personally i prefer external serial modems, never had a problem with any of them (granted i've only ever owned 2) the PCI based ones i've set up, so far have always been a pain, and riser modems i've never bothered with too much. Serial is straight forward - you plug it in, and they work. (i'm told this is a 99.5% phenomenon). USB ... works suprisingly well for mice and flash drives and the like but dunno about the modems.
Find a website that sells linux specific hardware and search for modems, some even tell you how to get the modem working under linux. Then go to the local shop (or wherever) and get that type of modem.
www.elx.com.au used to be good, can't claim i've browsed their stuff recently. other than that ... google.com/linux is also not a bad place for general stuff ...
From memory there is a (at least one) site that lists stacks of modem's and how well they work in linux / how to get them to work.
The beauty of external devices is, that the interface is usually compiled via the kernel, whereas PCI often times raises issues when you update your kernel...
