Randolph is a legendary blacksmith. He will send you on several errands to kill immensely powerful foes. Even though those enemies are one of the most dangerous you will face in the game, you should still complete those quests - each one of those will reward you with weapons made by Randolph himself. Some of those weapons are really worth the effort - especially Zwill Crossblades, the best daggers (and arguably the most powerful weapon) in the entire game. You can start all of the quests by speaking to Randolph - he can be found in Lestallum.
A Legend is Born
Recommended level: 55
Requirements: finish chapter 15
Target: - Bennu, vulnerable to Polearms, Machinery and Lightning, resistant to Ice, immune to Light.
Reward: 8,000 EXP, Iron Duke (Greatsword)
Once the quest starts, a new marker will appear on the map, pointing to the location of Bennu. As you can imagine, this encounter will be the easiest from the series of "legendary quests". The enemy won't deal any significant damage to your party, although it has a huge health pool and defense, making it extremely durable. You should aim at the legs of the enemy - after several hits the bird will fall to the ground and enter "vulnerable" state, allowing you to deal increased damage to the bird. Remember to use Amiger whenever you can - a single use of that ability should be enough to take over a half of the enemy health.
Once the encounter is over, head to Randolph to finish the quest and start a new one, Dreadful Legend.
Recommended level: 65
Requirements: finish "A Legend Is Born" quest
Target: - Malbadoom, vulnerable to Daggers and Ice, resistant to Greastwords, Fire and Light.
Reward: 10,000 EXP, Dragoon Lance (Polearm)
The enemy can be found in the Vesterpool region. Malbadoom is basically an enhanced version of Malboro, the boss you've fought at the end of chapter 10. The enemy is accompanied by a number of Malboro Brats, although you should completely ignore them and focus your entire attention to the main target. The best tactic is to use Daggers enhanced by Ignis' Enchant ability - this will allow you to deal significantly increased damage. Watch out for the "breath" attack of the enemy - it deals rather high damage, although during it the back of the enemy will be completely exposed, allowing you to easily warp there and attack the vulnerable part.
Once the encounter is over, head to Randolph to finish the quest and start a new one, A Legend Wrapped in An Enigma.
A Legend Wrapped In An Enigma
Recommended level: 75
Requirements: finish "Dreadful Legend" quest
Target: - 2x Sir Tonberry, vulnerable to Daggers and Light, resistant to Greatswords, Fire, Ice and Lightning.
Reward: 12,000 EXP, Ziedrich (Shield)
The enemies can be found near Tomb of the Tall, in the southern part of the map. Those foes will appear in the area only during the night - if you travel there during the day the area will be clear. Sir Tonberry (and "Tonberries" in general) is without a doubt the most annoying enemy in the game - he can deal huge damage and kill a character with a single strike (causing Instant Death), has absurdly high health pool and is incredibly mobile. The enemy is vulnerable to Daggers and Light, making Orichalcum daggers extremely effective against him.
The best and at the same time the only method to deal with those enemies is to rely on blocks and counters - wait for the parry prompt to appear on the screen and unleash your counterstrike. There's no point to launch series of attacks on the enemies, as the enemy can easily counterattack, killing your character in 4 or 5 blows (or in a single, if it's an Instant Death-type). When one of the enemies is gone you can start attacking the other Tonberry, although you should still focus on defending.
Once the encounter is over, head to Randolph to finish the quest and start a new one, Cursed Legend.
Recommended level: 85
Requirements: finish "A Legend Wrapped In An Enigma" quest.
Target: - Phalaris, vulnerable to Greatswords, resistant to Polearms, Shields, Fire, Lightning and Fire.
Reward: 12,000 EXP, Soul Saber (Sword)
The fourth enemy, Phalaris, is quite difficult because of an unusual reason - the arena you will fight it on is extremely small, especially given the size of the beast. You must watch out no to step out of the boundaries (red square on the mini-map) - otherwise the enemy will quickly regenerate vast amount of health. A weapon from Greatswords group is the best to use against this beast.
The enemy uses two attacks that cannot be blocked or phased through - "stomp" and "roll". This is why you should move around the battlefield all the time, trying to stick to the back of the enemy, performing a number of attacks and quickly changing the position again, preventing the beast from hitting you with one of the above mentioned attacks. Additionally, it's worth to target the legs of the enemy - after several strikes the beast will fall to the ground, allowing you to easily deal some extra damage. Armiger is your best weapon here - each strike while in this mode will deal several times more damage than a normal one, which should allow you to take out more than half of the enemy's health in a single go.
Once the encounter is over, head to Randolph to finish the quest and start a new one, Wondrous Weapon
Recommended level: 99
Requirements: finish "Cursed Legend" quest.
Target: - Naglfar, vulnerable to Fire, Ice, Lightning and Light, resistant to all other weapon types.
Reward: 20,000 EXP, Zwill Crossblades (Daggers)
The last foe is a real monster - Nalfgar has 120th level (!), an absurdly high amount of health points and most of his attacks will kill with a single hit. There's no point for you to invest in defense/health boosting items and meals and you should just focus on increasing attack. Also, remember that the enemy will appear only during the night.
You should replenish your supplies of Elixirs and Phoenix Downs before the encounter - those will be used to heal everyone during the fight. The enemy is resistant to most weapon types, although those from the Royal Arms group, as well as weapons imbued with Light, deal increased damage to the foe. The best weapon to use against Nalfgar is the Star of The Rogue - it deals immense damage, allows you to easily close the distance to the enemy and the health loss from using it isn't a problem, as the enemy will kill you with a single strike regardless of your health.
Armiger is extremely effective against Nalfgar - once activated, your attacks will deal huge damage and Noctis will be invulnerable for the duration of the ability, giving you the opportunity to significantly decrease the health of the enemy. This encounter is a typical "war of attrition" type - you will use a large number of items here, but the fight itself is fairly simple and doesn't require any specific approach. You just have to dedicate some time and items to it and the powerful beast will soon be dead.
Once the encounter is over, head to Randolph to finish the quest and acquire one of the best weapons in the entire game.