Apparently, according to Pieter Wuille, it was always the recipient that specified the script via the receiving address. So I'm imagining the only change brought by P2SH was to hash the script portion in the address, making it constant-sized, is that the case?
EDIT: I don't see where the script enters in the steps described here though... It only comments this
So I suppose there are different algorithms for the production (and parsing) of an address, the one described on that page only concerns "classic addresses".
Well, in ordinary "pay to pubkeyhash (address)" transactions, the script is written by the sender. But your client doesn't think that it is a payment to your wallet unless it is written in a very specific way. If it isn't OP_DUP OP_HASH160 {your key} OP_EQUALVERIFY OP_CHECKSIG, then it isn't really "to" your address, and your node will ignore it. Maybe you can redeem it with your key, or maybe not. If a sender points to some gibberish transaction and claims that it is valid, the alarm bells in your head should be going off.
In P2SH, you create the script yourself, and hash the entire script, including any and all pubkeys needed to redeem it. If you do that, when you see a transaction to the P2SH address (which is an encoding of that hash), you can spend it as usual. If someone else gives you a P2SH address, and claims that it is for you, then again, alarm bells.
Things can get murkier in multi-sig transactions, but you aren't going to stumble into that situation by accident, you'll get there because of an existing trust relationship. For example, you may pay to use a service that protects your wallet by storing a second set of keys, and then they can generate P2SH multi-sig addresses that can only be redeemed with both one of their keys, and one of your keys. How much you should trust payments sent to those P2SH addresses that you were given will depend on how much you trust that service, but again, you aren't stumbling blindly into this situation.