Do I have to complete each followers quest to get their perk or is it enough to just max out their relationship with little things (like lockpicking for Piper)?
The vast majority of companions do not have quests which are required to get a perk. You simply need to max out your reputation.
The exceptions are MacCready, Curie, Cait, and Nick Valentine. You'll need to complete each of their quests to receive their respective perks. While the quests are only offered when you reach maximum affinity, it's possible for affinity to decline between when you are offered the quest, and when you complete it, which means you might not get the perk immediately upon completion of the quest, as both requirements must be fulfilled simultaneously. Simply butter them up a little bit once more to get back to max affinity, and you'll gain the perk.
Some followers have an additional quest after recruitment that needs to be completed before you can get their perk.
These followers include Cait, Curie, Danse, MacCready, and Valentine.
MacCready, Nick, and Cait have all idolized me before I finished their quests, but I didn't get the perk until the quest was finished. Regardless of how many times Danse loves something, he can't idolize you until his quest is finished, at which point the perk is also awarded.
It's also possible to finish a follower's quest and not get the perk, due to insufficient approval. I've finished Cait's quest, but still needed to butter her up some more before I got the perk.
These are the needed quests for each companion: