I started writing last night, but got interrupted putting DD to bed and didn't get back on.
You have a couple of options:
The changing tables in most of the restrooms are actual counters, about counter height (34-35 inches from the ground). They are sturdy counters made of stainless steel or tile, so you could disinfect them easily before you use them. They are at least 36-40 inches long, some longer than others. Some of the smaller restrooms don't have a changing table, but the large ones do.
Some of the Companion Restrooms have the same type of changing counters as the regular restrooms. Some of the Companion Restrooms are not that large and don't have one.
First Aid might be your best choice. They have individual rooms or cubicles with low cots that are upholstered with vinyl (easily cleaned).
If the cots are too low (hard on your back), they also have doctor's office type exam rooms with higher tables, many of which can be raised or lowered to your needs.