I set this up recently, and some services will not work with Linux. They require downloading and running some software that manages the connection and, of course, this won't work in Linux. NetZero falls into this category, even though they offer software in the Linspire distribution. I could never get it to work in Slackware.
I use Copper.net for the dial up connection. It does not require special software, and is Linux friendly.
Surpluscomputers.com sells an internal hardware modem that works fine in Linux for about $15. A serial modem is going to be more like $50.