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)?
UPDATED:
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.
Original answer:
Yes, there are set and legendary items.
Many of them will be available through crafting, requiring the recipe to drop.
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.
According to this and a post from Bashiok, set items are legendaries, with the special exception that they do not drop until level 60.
Bashiok: Set items are now legendaries defined by a set bonus. They’re crafted items while leveling (recipes can be found that grant the ability to craft all the items in a set), which allows someone to really invest in filling out a set before they out-level it. Then at max level we’ll drop set pieces normally.
Before level 60, legendary items with a set bonus can be crafted if you have the recipe and a sufficiently leveled blacksmith. A list of legendary items with set bonuses is available here. Note the lowest level items listed require level 20.
Yes, Diablo 3 includes both Set and Legendary items, but they are quite rare. (Set Items are reportedly just as rare as Legendary items)
Legendary items run the gamut from low levels up to the level cap (check out this level 9 axe, for instance)
Set items exist at lower levels as well, though (from what I can see) only sets made by the rare Blacksmith plans, and it's not till level 60 that you get non-crafted set pieces.
Legendaries can drop any time; I got Wirt's Original Leg on Monk below lvl 10 (and only around 10-20% MF or so). Many low level ones don't really have the stats to be worth it; but if you just want a legendary to start off your collection, then perhaps the best option is to hunt for Rakanishu - and his blade is also needed for an achievement if you collect those ;).
Edit: There are some magic items with flavor text (such as Wirt's Leg), these are not legendaries.
It is not at all surprising to not encounter any legendary or set items on the first runthrough, but it is only because they are so rare. There isn't a point where they start having a chance to drop.
I have played about 200 hours now and have found exactly 2 legendary items. I do not know if it is intentional, but to me they are actually harder to spot than normal items when they do drop, orange/gold blends a little better than white. So maybe there were others that dropped and i missed them. I couldn't tell you what dropped the first legendary item, but it was in Normal. When I saw it on the ground I was amazed that it was just lying there in orange i think it just said Gloves. anyway, the second one wasn't until Hell, and it came out of a barrel or something, not a monster or chest, and I had +113% Magic Find.
If you want a whole set, your best bet is the Auction House.
Yes they were much more common in Diablo 2.
