Something else to consider is that for compatibility with pre OS 3.0 devices, Core Data (SQLite) isn't really an option.
Besides Core Data's (un)availability, I'm not sure that the data you need to store maps cleanly onto a relational data model. I'd lean towards the plist storage. I think it makes the most sense given your needs.
If I understand you, you want:
A list of genres, each containing a list of locations, each containing a list of qualities, each containing either a set of data (including URL) or just a URL. Either way, you can do this as a property list, and its just getting the the borderline of where you want to be with a property list as opposed to a database.
SQLite is on the iPhone, accessed by the standard C function API, although Core Data is not. SQLite would certainly allow you a lot more structure to your database and your queries.
Either way, you could include some sort of seed ID for the database, and then query an online server to receive just differences and that would reduce the need for transfering a large database over the net - but you'll need to determine just how large your database is before deciding on whether that is worthwhile. Simply compressing the XML file might be all that is needed, since the XML would compress a large amount (probably to ~ 30% of its original size).
Alternatively, you probably only really ned the area-appropriate sections of your database.