Gcc -Os или -O3?
Нет, размер и скорость - противоположные оптимизации. 
Уменьшить размер программы можно, путем устранения inline-вызовов, что приведет к тормозам.
Другой пример: ускорить программу можно, заменив циклы на линейные наборы инструкций (loop-unroll (его и включает -O3)), что опять же увеличит размер бинарника.
Нет, это не так. Это было бы так, если бы команды выполнялись бы линейно и занимали бы одинаковое время, но у нас есть циклы и функции, а также не все команды занимают одинаковое время. 
Есть важные оптимизации, которые сильно увеличивают размер программ, но в тоже время уменьшают время выполнения. Это:
- инлайнинг функций, когда код функции вставляется в место вызова. При это тело функции получается продублированным несколько раз в разных местах, но экономится время на вызовы (команды перехода, упаковка-распаковка аргументов)
- анроллинг циклов. Вместо того чтобы выполнять цикл по одному элементу 1000 раз, быстрее продублировать тело цикла  например 4 раза и выполнить получившийся цикл 250 раз. Время экономится за счёт уменьшения количества условных переходов.
- векторизавция
- и некоторые другие