Hello!
If I understood you right, you want to know what cities can you discovered without any previous quest to access.
So based on it, there is the cities I have discover without any kind of pre-quest, you will need to walk a bit much but there isn't any prequest requiered.
- Thais: (You should need a Key to enter into Fibula)
- Ab'dendriel (You should need a Key to enter into Draconia)
- Venore
- Kazordoon (Maybe you will need some keys to discover a part of the city if the doors are closed)
And I also would like to add those Cities where you can easy finish with a short "quest":
- Carlin (Access to the Isle of the Kings).