An algorithm called Public Key Recovery exists for ECDSA, which lets you construct the public keys for which a given pair of message and signature would be valid.
To explain the algorithm, remember that ECDSA signatures are pairs (r,s) for which sR = mG + rP. In this equation m is the message hash (which must be a hash of a known message), P is the public key (an elliptic curve point), G is the curve generator point, and R is a point for which R.x mod n = r. n is the curve order.
Rearranging this equation you get rP = sR - mG, or P = (s/r)R - (m/r)G. Thus, it seems we can just compute the public key from the message and the signature. Unfortunately, there can be up to 4 different points R for which R.x mod n = r (in practice, the number is almost always 2).
This technique is used in the message signing, allowing the signature to be verified against just an address, rather than a public key. The verifier in this case recomputes the public key from the message and the signature, converts it to an address, and then compares with the provided address. The address input is still required to prevent people from just giving a signature and message, and then seeing an address and thinking this implies the signature was valid. It must be compared against the expected public key or address to be the case.
The reason this isn't implemented for P2SH or BIP173 addresses is because the "standard" was never extended to incorporate those address styles. There is a proposed new standard (BIP 322) which would cover all types of addresses and more, but isn't widely implemented or used yet. BIP 322 also doesn't use pubkey recovery anymore; it simply uses the Script language and encapsulates a scriptSig/witness to verify against the script that corresponds with the address.