The secret to inviting people is in having a winning personality and having a slick website, magazine, facebook or some other way for players to SEE something proving your free company exists and looks fun. I won't lie I have the advantage of being a leader in a large Free company which is exceptionally well know. None the less I've built guilds in other games from bottom up.
In FFXIV you want to first have a very nice but planned approach, general conversation and baited question (proposing an invite), followed with a link for more information. All of my BEST invites were driven through fate groups or idle chatter in main cities. Often times I approach people and <tie ribbons in their hair>, <bobble a wiggly nana bear in their face>, <take pictures of their cute outfit>, or some other silly but non-evasive emote. This usually follows with partying with them doing fates, or talking to them in /say or /whisper. After seeing how they respond in general conversation I will ask if they've been in a company recently, and if they're looking for another, and that they are a fun/interesting/silly/cool person who would be great in our FC. Again I'm trying to generally compliment them before trying to sell them on the importance of my company itself. Most people will respond maybe, not interested, or kind of looking at X right now. I pretty much universally follow this with a comment that "You should totally check out Terra @ website if you have some time. I would totally be happy to invite/kidnap you and your friends." I ALWAYS in my followup statement add "you and your friends" most people travel with others and so when joining a new FC they want themselves and their friends to be welcome. Sometimes I'll chat a bit more with them, and often times they'll add me as a friend or I'll add them (if they're ok with it). Most of the time people will NOT join up during the conversation itself. Rather I end up hearing back from them an hour or two later and they want to join up or apply.
While this approach requires investment the people who end up joining genuinely feel like the FC might be worth their time. And odds are if you are fostering this type of approach, its quite likely the people you have and are inviting are happy cool people to be around (and shows in your FC itself). This is exactly how we operate in Terra and how I try to teach our officers to approach others.
As for finding people I generally pick out midlevel and higher zones where fates occur, and do fates while looking out for people without FC tags. Costa de Sol is a favorite of mine for doing this. But I also keep an eye out for people in the trade alleys in big cities and gear exchanges places like Idyllshire and Mor Dhona.
I absolutely never do /shout or /partyfinder. And if I search for people using the social feature I zone into their area and find them in person before engaging them.