Leading Parties

Play Nice

That's really the first rule to leading good parties, playing nice with everyone. Conflicts are going to arise in parties on occasion; first you should try not to be the source of those problems, and second a "nice" approach works best to resolve issues when others create them.

It never matters who's wrong, you'll be seen as a better leader if you can convert a bad situation into a happy one. Just listening to everyone is a big first step. Here are some suggestions:
Ask upset party members to send you tells so you can listen to their concerns. Wait till they've got it all off their chest, then agree with them (even if they're wrong). That will usually disarm them, and they'll like you and think you're doing a good job as leader, which you are. Next you can ask them what they think you should do about it. Don't be afraid to admit you don't know of a good solution, especially when it's true.

Party Types

Leading Exp Parties -Experience point gaining parties are the most common type you'll want to lead. When should you start them? What job combinations do you want? Where should you go? All this and more!

Leading BCNM Parties -Specific BCNM strategies are covered elsewhere, but there are many general topics you'll need to be versed in, such as: Who to bring, how to find the right jobs when there's no good information,loot split options, etc.

Leading Quest Alliances -This broad category includes AF coffer parties, specific item farming teams, mission alliances, and actual quest-completion party organization.

Searching and Inviting

The specific party type sections will deal with what jobs you want, but there are general skills you need for finding people, selecting from multiple seemingly equal choices, and convincing them that they should join you.

Searching
One of the most valuable command sets in the game are the search functions. The menu-selection thing is okay, but all the best searching is done via the text input.
/sea this is the start of your search command, short for /search.
inv "invite" this term in a search string will find characters who have their seek party flag up
__##-## restricts the level range of characters returned in the search. anon players will not be found.
__Rdm finds only Red Mage characters. The other 14 are pretty obvious: Blm Smn Whm Brd Nin War Drg Pld Rng Mnk Sam Thf Drk Bst.
abcd anything you enter that is not one of the specific terms will result in finding characters whose names start with those letter. "Nar" for example, will find you players named "Naria" "Narcolepsy" "Narrynarrynunu" and "Narcophile."
Rank # finds players who are exactly the specified rank (#). I used this when trying to catch up on a few missions: "/sea all rank 6 bastok"
additional terms you might want to use: Galka, Mithra, Hume, Tarutaru, Elvaan, Bastok, Windurst, Sandoria.
all tells the search to return players from everywhere in the world. This is very important most of the time.
region this term searches not just the zone you're in, but the whole region.
zone-name searching specific zones can be very useful, especially if you're deciding to go there (more on that in leading parties). There are some rules to this: first you cannot search a zone you've never visited. This also applies when you try to search "all" - you only get back places you've been. Second you have to use the standardized name for a zone, which is not always what you might guess. You can find the zone names by using the search from the menu. Examples: crawlnest, kuftal, promydem, garlaige.

Choosing
Be warned! None of this part is absolute law, this kind of thing is very subjective. I can really only tell you what I like to do, and from that you can extrapolate what you want to try. Personally, I always pick friends and linkshell members first. I'd rather have an entire party from my social linkshell, even if we're not an "ideal" job mix, than party with strangers. Part of that is what KA is though, we're friends that like to FFXI together, so it's almost a circular argument really.
With "random" people, if there is more than one player of a job I want, say two Whms seeking, here's what I do: I check their comment. Will they level soon and if so will that affect our party? Is their comment well-written and/or interesting. For jobs like Whm or Smn do they have Erase or Fenrir? Is their subjob maxed out? (I never take anyone with an underlevelled SJ, they are clearly not enthusiastic enough to be an outstanding party member, so why should you waste time on them?) I also do look at Rank too. Higher ranked players are usually (not always) more experienced, more likely to have great gear, and more likely to understand what makes a team work well. Remember, we're making a party with a specific goal in mind, and you're choosing among people you don't know. You might as well pick those most likely to achieve those goals for you and for the rest of your party. See Note, below.
Don't hesitate to ask them some questions in tells before inviting them. Find out if they want the same things you do from your party.
A few things I don't worry about: their race/job matching. This never seems to indicate if they're good players. Galka whm? they probably want to be different and are working extra hard to prove they can do it. Their nation - sure Bastok is the best, but it doesn't really matter (unless you're doing the mission for a particular nation, of course!)

Inviting
I have gotten the best results overall by using a simple and auto-translated tell asking directly if they want to join me. "(Experience Points) (Party) (Do you need it?)" or "(Bastok) (Mission) 6-2 (Help me out!) (Please)." I use auto-trans for 3 reasons. First, it's faster than typing it all out. Second, the use of a standardized message makes it very clear to the other person what you want, and it usually prompts them to auto-trans back a clear and precise answer. Third, I often ignore language when I search for people and the habit allows me to communicate with JP and NA players alike with relative ease. The bonus reason is that all the cool people use auto-trans words a lot in regular sentences, and I am, naturally, cool.

If there is only one player of a particular job you need. Ask them first! Once they've agreed, I usually rapid fire a message to one of each of the other jobs I want. After those respond I ask another round to fill in any holes I still have. It's no fun for anyone if you get 5 members but miss out on the critical job (the only seeking tank or regenner) because you didn't lock them in first. The exception to this rule comes when there are, say, exactly 5 people seeking in your range for your chosen activity, and they'd make a good mix. In that case you can gather them all and say "we have almost everything here… just need the one last one" and then try to harass non-seekers or wait for the last job to appear.

etc...

NOTE: If you just want to mess around, pick people with the lamest or most joke sounding names possible, who are rank 1 with no SJ. Those players are likely to be interested in joking and doing silly things. That's fine if that's what you want, but we're talking about goal-oriented parties here.