For your very first class, all you need is the Hunting Log and the Main Story Line Quests. These will level you easily without touching anything else until the 40s (though you may wanna do any FATEs you run into for gil and extra EXP and later seals). You can leave ALL the sidequests for later classes to help you leveling a bit . If you are holding out for Rogue/Ninja, I suggest you get PUG to 15 and stop there until the patch comes out (oct 28), so that you have as many story missions as possible available for your Rogue/NIN. Level some gathering classes if you get bored in the meantime. You will always need the crystals you get from gathering.
Your biggest EXP gain is currently dungeons (starting at lvl 15), but as a DPS, you will have long wait times. Use these wait times to do FATEs and Hunting Log entries.
For any later classes, you will be doing a combination of dungeons and FATEs as well.


Also, the absolute only cross-server activity is Duty Finder parties, sorry. You cannot friend, blacklist or message people on other servers, nor party with them on purpose.