I worked on some large commercial software for Linux for many years that had to support a wide variety of Linux installs (old and new), I can vouch for it not being easy. The technical side of supporting Linux in this environment can be very difficult.
There are, as you note, issues with the locations or presence of certain files, directories, and scripts. That's one part of the problem, but probably the easier one to solve (we had a whole big function that would try to detect how to open a URL by checking for xdg-open and older variants, checking configuration for KDE/GNOME/etc., and then falling back on detected browsers). This also has to be done for opening arbitrary files using their assigned program.
What's more complicated are library dependencies. Depending on system installs on GTK+ isn't always enough. You may need features not available on that install, due to version issues. You may have to work around versions of system libraries that have a bug present on one particular distro due to a custom patch.
Themes and icon sets are a problem if you hit any version compatibility problems. Your UI can appear broken if you reference icons that aren't registered on that system (generally an issue on older installs). This actually gets complicated quick in some cases.
So as an ISV, you have a couple of options for how you approach all this. You can limit the distros and versions you support, putting out builds for each. This is a perfectly fine strategy if you can get away with it, but not everyone's going to be able to use your program in that case.
Another option, which is what we did, was to basically ship everything we needed along with the program. Libraries (glibc, gtk, x11, everything we were forced to ship for compatibility), icon sets, themes, etc. You then try to dynamically figure out which modules you can load from the system, and which you need to load from shipped modules. You also need to handle setting up paths for anything like icon sets and fallback themes you may need, and deal with the compatibility issues that can occur from that (older versions of the XDG icon theme spec didn't have a properly-functioning fallback system when specifying multiple icon theme directories).
If you ever need to do anything more specialized (support for hardware devices, anything using D-BUS on older installs, more specialized window management abilities), you run into a whole new set of issues.
These days I focus almost entirely on web-based software, so that sort of wide range of compatibility problems are entirely behind me. (Ahem.)