If you want to continue using dialup, then why not use the cheapest I have found thus far.
$5.95 a month no setup fee
It should definitely work with linux because the use of the connection software is not necessary.
When I was using dialup I used access4less same price as warp connect, (they have since been taken over by Earthlink) and I did not have to the connection software to get it to work in linux. I now have DSL with Cavalier.
Also if you're interested in DSL verizon is offering a $14.95 package this is not an introductory deal I think its 768K.