Right you are about narrow streets esp. in the older section of Cadiz; I know some of the hostals and or sister (to hostals) hotels have parking underneath - but can't remember which ones. Unless you are planning to stay in the old Jewish section - which I strongly recommend you do - parking isn't too bad. And figure, once you do park all the time you are in Cadiz will be walking so it is a one time shot.