This seems to be the answer:
waithidden curl -k --data-urlencode relevance="%22this=%2522that%2522%22" -o "{pathname of folder "__Download" of client folder of current site}\BaselineComponents.xml" --user {parameter "currentConsoleUser"}:{parameter "secret"} https://{parameter "RootServerURL"}/api/query
The trick was to escape the % in the %22 so having a literal quote requires: %2522 to “double escape” the quote. Also, I’m not sure what extra escaping –data-urlencode is doing as well.