I have been using EVDO broadband for the last few weeks and have been very pleased. We are actually in the same situation -- our house is a few miles outside of town, so cable/DSL are not available.
What I actually do is use my phone as a modem tethered to my laptop. My provider (Alltel) only charges $25/mo. if you connect like this. The only downside is that you cannot talk and use the net at the same time (you can receive calls while in data mode, but if you take the call you'll be disconnected). Also makes networking a bit more of a pain in the butt, you can't just buy a router and plug a card into it. They also offer a $60/mo. plan which uses the PCMCIA card. The main advantage of this would be the ability to talk on your cell and browse the net, as well as higher mobility (which doesn't sound like an issue for your parents).
Speed is as advertised, typically between 500-700kbps, although I have seen 1Mb+ on a few occasions. BUT, latency is very high, 300-500ms to US servers. Because of this, it may not seem much faster than dialup in some ways. For example, it takes just as much or maybe slightly more time than dialup for it to query and start loading a webpage. However, once it's started the images load up much faster. Fine for streaming and downloading. Useless for gaming and VoIP. I am using EVDO REV-0. EVDO REV-A, which has been deployed in and around some of the larger cities I believe, offers faster speeds and lower latency (250ms typical I believe, as opposed to 400ms for REV-0). Still not very good, but I guess even REV-0 is better than satellite.
You may also look into line-of-sight wireless. This was also available in our area, but tall trees around our house disrupted line-of-sight to the tower. Also it would've required installing a dish. The nice thing about the EVDO was we went to the Alltel office, had them activate it, bought the data cable, went home and connected to the net. Very painless installation.