You have no reason not to go to other cities. Each city has leves for all level ranges.

You can explore whenever you want really. However, you'll find it a lot more pleasant once you have a chocobo. On this note, getting a chocobo is going to require you to do a huge amount of world 'exploration' anyway.

Explore at whatever level, the level 90 monsters are going to one shot you no matter what level you are anyway.