What does it mean to have a complex signal?
Using complex numbers to express sinusoidal signals is hardly "just a notational convenience". 



On what it means for a sinusoid to have two orthogonal components:

First, realise that "orthogonal" is just a fancy word for "separate" or "fully independent".

Assume that you're dealing with a sinusoidal signal of fixed frequency \$ \omega \$. Such signals have two degrees of freedom - amplitude \$A\$ and phase \$\phi\$. That is:

$$
x(t) = \operatorname{Re}(A e^{j \phi}\times e^{j\omega t}) = A\cos ( \omega t + \phi )
$$

Information can be conveyed by either varying the amplitude or varying the phase, so there are two separate "channels" for information.

Equivalently, you can express the same fixed-frequency sinusoidal signal as the sum of two signals, phase-displaced by 90 degrees:

$$
x(t) = A_1 \sin (\omega t) + A_2 \cos (\omega t)
$$

Think of the sin term as a "vertical" wiggle, and the cos term as a "horizontal" wiggle. Again, these form two separate "channels" for communicating information. 

It is fairly easy to build equipment that separates the sine component from the cosine component, so this is used as the basis of practical communications schemes. See quadrature amplitude modulation (QAM).



On the physical meaning of "multiplying by \$j\$":

In phasor form, the phase of the signal is given by a complex number \$e^{j\phi}\$ like so:

$$
e^{j\phi} = \cos{\phi} + j \sin \phi 
$$

If you multiply by \$j\$ you get:

$$
j\times e^{j\phi}=j \cos \phi - sin \phi
$$
$$
j \times e^{j\phi} = j\sin (\phi+90^\circ)+cos(\phi + 90^\circ)
$$
$$
j \times e^{j\phi} = e^{j\phi+90^\circ}
$$

Which is to say that multiplying a phasor by \$j\$ changes its phase by \$+90^\circ\$. I like to think that two phasors \$A\$ and \$jA\$ are at right angles to each other, i.e. they are orthogonal.