Full Coupled Cluster (FCC) vs. Full Configuration Interaction (FCI)
The main theoretical difference is the way excitations are used. "Excitation" refers to putting one or more electrons in higher orbitals than the "reference" calculation, which is often a Hartree-Fock calculation, would. CI uses a "simple", linear excitation operator, whereas CC uses a more complicated, exponential one. One can think of CI as a sum of excitations while CC results in a product of excitations.
Symbolic equations for the wave function ($\Psi$) ansatz of either method read:
$$
\Psi^{\text{CI}} = (1 +C_1+C_2+C_3+...) \Psi^{\text{HF}} \\
\Psi^{\text{CC}} = \exp(T_1+T_2+T_3+...) \Psi^{\text{HF}} \\
= (1 +T_1+T_2+T_3+\frac{1}{2}T_1^2+\frac{1}{2}T_2^2+T_2T_1+\frac{1}{2}T_3^2+...+\frac{1}{6}T_1^3+...) \Psi^{\text{HF}}
$$
In CI, the excitation operator is often denoted $C$ and the prefactor of determinants are called CI coefficients, whereas CC uses $T$ and "amplitudes". In either, the subscript refers to the number of excited electrons.
For "full" calculations, that is, calculations that take into account every possible excitation, the results of CC and CI will be identical.
Full calculations are too expensive for all but the smallest systems, because the cost rises as $O(N!)$, where $N$ is some measure of the system size involving electron number and basis set size. For this reason, one typically decides to "truncate" the excitations to lower the cost.
Single-reference Truncated CC vs. Single-reference Truncated CI (this is what CC and CI commonly refer to)
Truncation first involves collecting the excitations into "classes" of excitations. Within a class, one gets similar cost and hopes for similar contributions. Thus, one may sort of gauge the cost and accuracy of the calculation. Standard ways of doing this have evolved, and this is what CCSD, CCSD(T), CISD etc. refer to. CASSCF/RASSCF can be categorized like this, as well.
With truncation, another difference between CI and CC arises: CC is no longer variational and CI is no longer size-extensize. Variationality is the property that the resulting energy has the true energy (of the given basis set) as a lower bound - one approaches the energy monotonically from above as more excitations become involved. Size-extensivity is the property that two identical systems at infinite separation from each other yield twice the energy of a single system. The latter property is thought of as the more important one, mainly because of its implications for closer, interacting systems. Variationality is also less of a concern because finite basis sets must be used, thus, one is typically far above the true energy anyway.
Another technical difference is that truncated CC and CI lead to different equations, for which different methods of solving have been developed. Overall, CC implementation is, or at least used to be, more difficult. Properties other than the total energy can also be more difficult to implement.
Scaling of CC and CI
Basically, when truncation is performed at similar levels, the two methods scale the same, but the prefactor may be different - this also depends on the quality of the implementation. For reasons stated above, CC has been worked on more intensively since, say, the mid 1990s. So, CISD and CCSD scale similarly, CISDT and CCSDT would as well. Bottom line: CCSD(T) will still be affordable for molecules where full CI would require specialized implementation on a dedicated supercomputer.