Locus Maps is a candidate capable of this (and of many other things). For some details, you might wish to take a look at my other answers recommending this app:
With the first two containing some screenshots. Here are some more, covering your specific request:
Locus Maps: Add a POI / Attach media
Long-pressing on a location opens a context menu, and lets you add a POI. You can write a description, and even attach media (not only photos, you could also place an audio note when too lazy to type).
Locus Maps is designed for outdoor activities, so off course it is able to work completely offline (though you can use online maps as well). Map sources are plenty, including e.g. OSM and Google Maps. Tons of addons available for more features (Geocaching and Augmented Reality, just to name two).
Concerning privacy: Locus Maps itself doesn't request access to your contacts. So if you're one who wants to directly navigate to addresses from your contacts list, you would need to explicitely install the contacts addon.
Referring to your requirements explicitely:
- Free: It has two free versions: one is free of charge, the other free of ads ;) On the project site, you can compare their features.
- Usable offline: Definitely (both versions)
- Runs on Android: Yes, AFAIK only there.
- Launches very fast, minimalist UI: Depends on what you call fast/minimalist, and on your hardware specs. A good compromise it is, but offering many features it's for sure not "absolutely minimalist"
- When I come back home I should be able to use the data on Linux: No problem, that's what I do (my only windows are those for light and fresh air). It can read/write e.g. GPX, KML, KMZ – at least the latter format (KMZ) should be suitable for your case, containing data, desc, and media
- Does not require Google Play Services: The paid version relies on Google Licensing. But speaking to the dev, there might be a way around that as well
- Does not require network/contacts permissions: No contacts permission, as described. Network is of course needed for maps and route planning, but it works well without a network connection: If you didn't download maps beforehand, well, then you get an empty grid (and mybe unable to tell where exactly you want to place your mark)
- Open Source: unfortunately not.
Naming an alternative:
Trip Journal: Main screen, report (source: Izzy)
Trip Journal is made for that purpose explicitely. You write your travel journal while on the road, and send reports before getting home. Works offline as well (with or without maps pre-cached), no Open Source, but a free and a paid version. Outputs to KMZ, but quite a heavy-weight variant with lots of JavaScript and stuff, so it only works with Google Earth. I can provide a How-To on converting that into a more light-weight variant (I figured out myself), but I'm not sure if it's still valid with their latest versions. Still, might be worth a look.
Differences to Locus Maps concerning your requirements: requires contacts permission.
