I think Phoenix is a great server to start on. There is at least one (although I believe I read another thread on ffxiah.com about another LS) LS that is dedicated to new and returning players. Check This
out. They also have a thread on the main page. Regardless of what you hear, I still see regular 6 man parties in the Dunes, Qufim, the Jungle. They may not be as plentiful as the GoV alliances, but they are still there.
Best of luck to you!