Starting in a particular city affects one thing and one thing alone. The initial 3 story quests or so.

You can level any job, go anywhere, be anything, join any company, etc.

Start in whatever city you'd like. You'll probably end up in Ul'dah at some point, you can do all your Gladiator stuff then.