What is the difference between "gcc -s" and a "strip" command?

gcc being a compiler/linker, its -s option is something done while linking. It's also not configurable - it has a set of information which it removes, no more no less.

strip is something which can be run on an object file which is already compiled. It also has a variety of command-line options which you can use to configure which information will be removed. For example, -g strips only the debug information which gcc -g adds.

Note that strip is not a bash command, though you may be running it from a bash shell. It is a command totally separate from bash, part of the GNU binary utilities suite.

The accepted answer is very good but just to complement your further questions (and also as reference for anyone that end up here).

What's the equivalent to gcc -s in terms of strip with some of its options?

They both do the same thing, removing the symbols table completely. However, as @JimLewis pointed out strip allows finer control. For example, in a relocatable object, strip --strip-unneeded won't remove its global symbols. However, strip or strip --strip-all would remove the complete symbols table.

Which one do you use to reduce the size of executable and speed up its running

The symbols table is a non-allocable section of the binary. This means that it never gets loaded in RAM memory. It stores information that can be useful for debugging purporses, for instance, to print out a stacktrace when a crash happens. A case where it could make sense to remove the symbols table would be a scenario where you have serious constraints of storage capacity (in that regard, gcc -Os -s or make CXXFLAGS="-Os -s" ... is useful as it will result in a smaller slower binary that is also stripped to reduce size further). I don't think removing the symbols table would result into a speed gain for the reasons commented.

Lastly, I recommend this link about stripping shared objects: http://www.technovelty.org/linux/stripping-shared-libraries.html

"gcc -s" removes the relocation information along with the symbol table which is not done by "strip". Note that, removing relocation information would have some effect on Address space layout randomization. See this link.

They do similar things, but strip allows finer grained control over what gets removed from the file.