To be honest, I see a lot of people say that it is hard to get low level parties. Consequently, newcomers often think that they will have difficulty getting a party.
I have leved 3 jobs to 75 in the last 6 months or so, and hardly ever had problems getting a party. This is on Kujata, where it seems we are not one of the most popular servers.
My recommendation - doesn't matter where you go. As someone else mentioned, if you know anyone who play's, go to their server so they can show you the basics. Once you get into exp pt's, learn about the setup's and when comfortable, make your own party. 95% of the time I make my own, and I hardly ever wait. I have been playing for less than two years and have 5 75's - The first one took me 6 months, so you do the math after that.
Regards,
Knoc