Hmm, lemme guess; your parents are 60-70 years old. Am I correct? My Mom is 70. My brother and I tried to get her WebTV for XMas last year, but she wouldn't let us. She said "I'll never learn to work the computer...it'll just waste away because I'll never use it." We tried and tried to convince her; to no avail.
Her sister (my favorite Aunt

) has WebTV and I email all the pics of my son and pics of my life to my Aunt, then my Mom goes over to her house and looks at them on my Aunt's giagantic 25" RCA television <sarcasm></sarcasm> Sadness, no?
I'm happy that your 'rents want to learn "that darn Internet thingee." Good for them!
I agree w/JCIV; a local established provider is best.
NO AOL - ever! I'm sure they have already mentioned AOL. They are ignorant (not an insult..they ARE ignorant of Evil AOL!) and don't know any better. Do not saddle them with The Ultimate Evil in Internet Access.
Here in Texas (Louisiana and Oklahoma too) we have Everyone's Internet.
(linky) and they charge a $30 hookup fee and then it's
$10/mo for life. Seriously. I had them for about a year, but I got tired of downloading 5-meg UT maps at 2.2kb/s Hahaha! If they offered DSL, I'd still be with them. Good luck.