Nothing much, just need a new modem. The one I have now (Aureal Software Modem) doesn't work with either Linux or Windows XP.
All I really need is a make/model of some of your Linux modems.

Hmm I dunno if this modem supports linux but its Very good. Hayes Accura 56k v92 Modem. I get a 120 ping on Counterstrike.

Any external hardware modem should work fine. For Linmodems, check Linmodems.org (http://www.linmodems.org).
Normal modems: Modem-HOWTO (http://www.tldp.org/HOWTO/Modem-HOWTO.html)

I'd like an internal one, for having an external would just be one more serial or USB port in use, another thing to unplug, another thing to find a little nook or cranny for...:dead:

Would this (http://www.intel.com/design/modems/products/536ep.htm) modem be alright? Any glaring problems with it?

Hmm, at least Intel has drivers for it:

http://www.intel.com/design/modems/support/drivers_linux.htm

So I'd say it should work then, just remember you have to have the necessary networking options included either as modules or builtin in kernel. If you haven't recompiled your kernel (yet ;)), they should be available as modules. I'm talking about PPP support and its options.