This is even more important than it sounds because the US federal goverment considers 100 miles inland from any international border (including the great lakes, etc) as being "the border". And that is where 80% of the people in the USA live.

That's incorrect, or at best misleadingly incomplete. 8 USC §1357(a) authorizes border agents to, "(3) within a reasonable distance from any external boundary of the United States, to board and search for aliens any vessel within the territorial waters of the United States and any railway car, aircraft, conveyance, or vehicle, and within a distance of twenty-five miles from any such external boundary to have access to private lands, but not dwellings, for the purpose of patrolling the border to prevent the illegal entry of aliens into the United States."

The associated regulations, 8 C.F.R. §287.1, interpret "reasonable distance" to mean up to 100 miles from the actual border. But: "In fixing distances not exceeding 100 air miles pursuant to paragraph (a) of this section, chief patrol agents and special agents in charge shall take into consideration topography, confluence of arteries of transportation leading from external boundaries, density of population, possible inconvenience to the traveling public, types of conveyances used, and reliable information as to movements of persons effecting illegal entry into the United States."

The statute and regulation just mean that agents don't need to patrol the border at the literal border--which in some cases runs through the middle of bodies of water. But they must justify the determinations of what's a "reasonable distance" from the border must be based on what's needed to prevent illegal entry into the United States, based on factors such as topography and transportation routes.

There's Supreme Court precedent establishing that this isn't the case. ACLU itself had backed off it, last I checked, but since they used it for a very long time in fundraising, people will never, ever stop believing that 80% of the United States lives in a "Constitution-free zone". You cannot in fact be border-searched on the streets of Chicago; in fact, you can't even be border-searched at a lawful fixed immigration checkpoint.

Border searches need a nexus to an actual border crossing.

I'm reading the statute this comes from [0] and its associated definitions [1] but I don't see that it's as bad as you made it sound. (I don't love it, still.)

The 100 mile "reasonable distance" is used to define where vessels and vehicles may be searched for aliens.

But the warrantless search may only be applied to persons seeking admission for whom an officer has suspicion of reasonable cause for denying the person entry.

Of the 80% of people living within that distance (which is an upper bound, btw; the agents in charge are required to set a bound not to exceed that by taking into account such things as "density of population, possible inconvenience to the traveling public.") almost none can be suspected of being under reasonable cause for denial of entry.

So to do the thing you are fearing, 1) the chief patrol agent has to set the distance to encompass an inappropriately large area in violation of this law, 2) an agent has to stop and search cars randomly, and 3) somehow become suspicious that an occupant is seeking entry and ought to be denied entry, and 4) believe that searching that person's device would reveal information demonstrating that the suspicion is correct.

It's not great, but it's not "80% of Americans can have their devices searched without a warrant".

[0] https://www.law.cornell.edu/uscode/text/8/1357

[1] https://www.law.cornell.edu/cfr/text/8/287.1

Including 100 miles from international airports?