What’s the “best” tool depends on your criteria for a tool. You’ve provided what you need for capabilities as a map. That’s great and very important, but doesn’t really tell us what you need as a tool. I’m not asking you to provide such criteria, this is just a disclaimer for why Google maps might not be the best tool even though I personally would definitely use the Maps API. It’s readily available, and well supported by both Google and a Maps community. The API is very powerful, I’m not sure there’s anything one couldn’t do with it with enough effort. For me, it would be the best mapping tool for websites. YMMV.
You can store the data you need in any manner you like. The WP data objects like posts and taxonomies are obvious vehicles for this and I don’t see why you would not use them, but for the sake of discussion, you could store the data in a custom table and not use WP objects at all.
You should first look at the available mapping plugins and see if any of them might meet your needs. Unless you’re an experienced Google Maps coder, plugins could save you from climbing a significant learning curve. Even if they don’t quite work for you out of the box, perhaps it could be modified or extended to meet you needs. Good, well written plugins can be extended with your own plugin just like WP can be extended with other plugins.
With Google’s Maps API, the photos would be custom map markers. The API exposes methods to declare and display markers. When they are clicked, by default a data box is opened. You can put a link in this box or simply go to a new web location directly. How you store marker data within WP is entirely up to you. I’d suggest using a custom post type and post meta, but just about anything is possible.
Think about scalability. Having thousands of different map markers (photos) is going to really slow down your map. A lot of photos in one area of a map will be an unusable mess. You might consider more conventional markers and display the photo in the marker’s data box. The data box could be displayed/hidden as a roll over effect so it wouldn’t be too cumbersome to browse for images even though they are not immediately visible. It’s less than ideal, but even more so is a very sluggish map.
