Agree with the others, esp. Kurt on this one.
There are several times where a wine can offer complexity. Aromatics, flavors in the mid-palate and/or the finish/aftertaste.
I typically find more complexity as a wine evolves with age. That is not to say that a young or even infant Port can not show complexity, as I believe it DEFINITELY can. However, it is easier for most people to understand "complexity" when sensing the "layers" that Derek mentions. Those typically don't emerge for years after the Port is bottled.
In table wine, I find the Pinot Noir grape offers the greatest level of complexity for me, but Riesling and Madeira also show that in spades. For PN, the Burgundian expression epitomizes a mono-cepages ability to deliver surreal layers in all senses of the word complexity. However, Bordeaux lovers typically believe that the blend of the Big 5 - accounts for it being the most complex wine on earth. Then again, they typically don't like Madeira.
With Port there is a great discussion to be had and I think it will be put into a separate thread.