The high-speed option is DSL, which is totally tied to and dependent on your home phone line. As you’ve already found, DSL isn’t available on your line, because it’s simply too far from the phone company switching office. Even if you could get DSL on the home line, it would be useless for traveling.
For traveling, look for hotels that offer in-room ethernet jacks. They’re usually free in the sense that they come with the room, but you won’t find them at Motel 6 or other inexpensive “tourist” hotels - rather, they’ll be at the likes of Hyatt, Marriott and other “business” hotels. The buzzword they’ll probably use in the advertising is high-speed internet. This will require the laptops to have a standard ethernet (aka network) jack, and your travelers will need an ethernet cable.
Otherwise, there’s just no practical means of getting more than 56k out of a dial-up connection.
You could also investigate cellular modem internet service. On a good day, I can get a roughly 110k connection - twice as fast as dial-up, but there’s a big collection of gotta-haves for it to work. You gotta have a cell phone that can take a data cable. Your phone needs to be on a plan that offers data service. You need the data cable. Finally, you gotta be in a data service area, which is often the same as wherever a phone is getting digital voice service. Downsides are that it ties up your cell phone, so if you want to be online and talking, you’ll need two cell phones. It’s also a bit pricy. For me, the cable was $45, and the phone service needed a $6/month upgrade. The real cost is in the data. You think roaming is expensive? Try getting online during the day. Data service may be free during nights and weekends, though.
I’ll offer yet another option - WiFi. Seemingly everywhere you go, someone’s offering a WiFi connection. Boingo is one of the big players in this market - For something like $20-25 a month, you get unlimited access on their network. Otherwise, you can pay as you go, but that can add up, by the time you pay Starbucks $10 for a day’s use one day, and $4 for an hour at McDonalds and so on. On the other hand, pay as you go is better if you only need the service rarely. And of course, there are free hotspots out there.