When do set and legendary items start dropping?
I am almost finished with normal mode in Diablo 3 and I have yet to encounter a single set or legendary item. In Diablo 2, I started finding items like this right away that were appropriate for my current level.
Is there a certain time when they begin to appear (like in nightmare as opposed to normal)?
Legendaries can drop at any time, anywhere, albeit rarely. With the Loot 2.0 updates, new heroes from lvl 1-59 will get a guaranteed legendary drop for the first kill of The Butcher, Belial, Azmodan and Diablo.
Characters below level 11 are unlikely to find Legendary items, because they have a minimum level requirement. Currently there are no Legendary items available below level 11. (source)
For level 60 characters, you should get a guaranteed legendary drop from Diablo every time you kill him after resetting all of your quests and working your way back to him.
Higher tiers of Torment supposedly include an increase in legendary drop rates, but the exact amount of the bonus has not been disclosed. It doesn't seem to be major, though, so you should pick a lower tier of Torment over a higher one if you will kill significantly faster in the lower tier.
Note, however, that some legendaries will only drop in Torment I - VI.
Yes, there are set and legendary items.
Others will drop randomly, but extremely rarely. This can happen at any level, as not all legendaries are high level gear.
The best legendaries will be Inferno drops.
However, it has been stated that the very best items in the game will not be the set items or legendaries. Instead, the very best will be Inferno level randomly-generated rares.
Can you update this answer real quick for the new 2.0 patch? With change in difficulty tiers and the guaranteed legendary drops for the first-time boss kills (or after a quest reset).
@Doc I've updated my answer; I'm not certain if there is a correlation between difficulty tiers and legendaries, though, as there is no longer an implicit magic find boost in higher difficulty levels.
Higher ticks of Torment increase the drop chance of Legendaries. The amount is not specified, but it is stated in the difficulty's description. There are also some legendaries that only drop in torment difficulties.
@Doc The consensus I've seen is that farming for legendaries is pretty consistently faster at Torment I than at the higher levels, since any increase in drop rate is mitigated by the decrease in clear speed due to tougher mobs. The list you cited for Torment-exclusive Legendaries appears to be RoS only, and isn't yet live (and will probably only be available for those with the expansion).
This should be edited now that Reaper of Souls is out to reflect that set pieces for lvl 70 characters can only drop in Torment difficulty.