Star cluster explore missions now grant diplomatic experience if the mission ideals are in line with the Fed Diplo corps. Once you jump the first level, you can start being directed by Ambassador Sugihara.
I love the addition of the Diplomats. It is more in line with Star Trek in my opinion. I hear alot of people complaining about them but if you will be patient and think they are fun. I hope STO get more of these and make them more interactive I LOVE IT
The downside: You have to restart your career to benefit from all the chances, many of the accolades and XP's are not retro-active. That way it takes you a LOT of time and nerves before you even reach "Attaché" status. If you start fresh, you are an Attaché in no time. Grade 6 is a diplomatic mission with 10 DXP's, the Celes mission gives you even 160 full DXP's and of course it gives you the necessary hours of playtime which you need to advance.
I just ran into a slew of errand running diplomatic assignments at memory alpha.
You just answered your own question
There isn't really an "initial quest chain" or starting point. You can start your first FDC mission on a planet like Vulcan or Bajor or M-A, the station K7, or wandering the star clusters. As long as they don't involve combat they should grant Diplomatic experience.
People gripe how long it takes to get enough DXP to advance. I say, so what? Why is everyone in such a big rush to get to Vice Adm, Ambassador, or whatever? You guys do know there's a level cap right??