What does it really mean for a program to be legal or `valid or ``conforming?

Simply stated, the Standard talks about three kinds of conformance: conforming programs, strictly conforming programs, and conforming implementations.
A conforming program is one that is accepted by a conforming implementation.
A strictly conforming program is one that does not depend on any implementation-defined, unspecified, or undefined behavior, that does not exceed any implementation limits, and that otherwise uses only the features of the language and library as specified in the Standard.
A conforming implementation is one that does everything the Standard says it's supposed to. (The way the Standard says this is that a conforming implementation ``shall accept any strictly conforming program''.) There are two kinds of conforming implementation: hosted and freestanding. A hosted implementation is intended for use with conventional application programs; a freestanding implementation is intended for use with embedded systems and the like, and is not required to supply all of the standard library functions.
Unfortunately, neither of the definitions relating to conforming programs are as practically useful as one might wish. There are very few realistic, useful, strictly conforming programs. On the other hand, a merely conforming program can make use of any compiler-specific extension it wants to.
Other words you may hear are ``compliant'' and ``conformant'' which are basically just synonyms for ``conforming''.