Actually, AOL doesn't require use of their software. You can, with the number and your account name and password log on straight, or on linux use Peng-AOL or a few other programs. You can even setup imap mail for AOL so you never need to go to AOL.com for e-mail either.
Pretty much anything can work on linux if you can find numbers and in rare cases like PeoplePC specialized dialers. Why you would want dialup is another story, but I won't go there, I will just assume you have a good reason.
I would recommend local. Most national dialups cost a fair amount in comparison to locals, and considering if you even wanted to use 3d accelerator and other...dial up enhancements... you can't usually on linux(they require software working with the other end to compress, and your local decompressing files.) So Web Accelerator 3g and others, which don't work anyway on any page made by someone who knows how to make images for the web, won't be available so most nationals are what, 9.95 without that? You should be able to find a local provider like you phone company for 4.95 or so.