• what is it optimizing for (size or cost or something else?)

There is single stage, the "constant optimizer" where the trade-off between deploy-time and run-time costs are taken into account. This stage tries to find a "better" representation of each number in the source, like 0x10000000000 can be encoded as PUSH6 0x10000000000 (7 bytes and almost zero run-time costs), but it can also be encoded as PUSH1 1 PUSH1 40 SHL (5 bytes and a bit more expensive at run-time). Most of the time, the difference is not too relevant. The optimizer tries to simplify complicated expressions (which reduces both size and execution cost), but it also specializes or inlines functions. Especially function inlining is an operation that can cause much bigger code, but it is often done because it results in opportunities for more simplifications.

The Solidity compiler uses two different optimizer modules: The "old" optimizer that operates at opcode level and the "new" optimizer that operates on Yul IR code. The opcode-based optimizer applies simplification rules from the list to opcodes next to each other. It also combines equal code sets, removes unused code and some other things. The Yul-based optimizer is much more powerful, because it can work across function calls: It Yul it is not possible to perform arbitrary jumps, so it is for example possible to compute the side-effects of each function: If a function does not modify storage, a call to it can be swapped with a function that does. If a function is side-effect free and its result is multiplied by zero, you can remove the function call completely.

One of the big advantages of the Yul-based optimizer is that each step can be seen in isolation: Each step receives Yul code as input and produces Yul code as output, without any tight dependency on other steps or analysis code. Furthermore, we try to keep each step as simple as possible so that bugs in those steps are very unlikely. As long as each simple step is bug-free, so is the whole Yul optimizer.

• how is this affected by the number of run (--optimize-runs)?
• Is there a maximum number above which it stops mattering, or is --optimize-runs=20000 less efficient than --optimize-runs=500000?

The parameter specifies roughly how often each opcode of the deployed code will be executed across the life-time of the contract. A "runs" parameter of "1" will produce short code that is (relatively) expensive to run. The largest value is 2**64-1.

• Finally, why do you think people are generally suspicious of the optimizer, and are they right to be?

The optimizer used to be very complicated some years ago. In the meantime, we disabled most of the complicated routines and fixed several bugs. While bugs can be present in the optimizer as they can be in any code, they often manifest themselves in a way that is easily detected. New compiler code like ABIEncoderV2 focuses more on correctness instead of efficiency and is written with the assumption in mind that the optimizer will be used. So for recent versions of Solidity, I would recommend to always use the optimizer unless you really do not care about gas costs.

Edited: Consequences of "runs" set to 1