A Legacy server is a server that's been in use since 1.0 (3+ years). These servers are established and populated, but most people have a number of jobs leveled so it might not be the easiest for new players to adapt to. They do, however, tend to have active endgame communities. All other servers were establish either at ARR/2.0's launch or since then. You can join any world regardless of region. The EU servers and the NA servers are currently located in the same data center in Montreal, Canada. SE is in the process of spinning of the EU servers into there own data center in Europe, but that was just announced last weekend, so I would expect for that to be at least six months (or longer) from happening. I've heard a lot of the Oceanic community plays on Tonberry and Masamune (Legacy) on the JPN data center for better ping. It kinda depends on what is your priority, games responsiveness or a large English speaking community.

If you do decided to roll on a Legacy server be aware there was a patch today so its likely that the Legacy/higher population servers will be locked for character creation for a few days. If the server has many characters logged in, they will shut that server down for new characters until some people log out.