It's also just that they're weird and not terribly melodic. They're great, but it's not like some jazz standard from a musical where you just kind of feel where it's going after hearing it a few times.
But I acknowledge that in that context, it's an "out there" harmonic adventure which builds tension, to be released when the final section harps on the tonic.
I still think that it's mostly the tempo that makes Giant Steps feel alien. Modulating through major keys by major thirds isn't that exotic, but doing it so quickly that ear just doesn't get a chance to orient itself is.
On more straightforward changes, I can usually internalize the melody and harmonic motion well enough to form a sensible solo, but I've got my limits. Fortunately the era of "Giant Steps" getting called on every gig has more or less passed.