My favourite is LazyestGallery. It is quite complex and a bit strange in some places (it has an option to use table markup for grid layout!) but is super versatile. You can indeed nest galleries as you wanted in addition to cool features like being able to create galleries and sub-galleries but simply placing images in certain directories through FTP.
Other than your last requirement, that plugin would fit the bill perfectly. It has an option for slides which would give you the previous/next capability for images within each gallery. When you upload an image, you also have the option to enter in a description (I don’t need this feature so it’s disabled in the example I gave you).
However, the idea of related content would indeed be difficult to achieve with that setup. Besides that, it looks like the main focus in those boxes is the content and image is there as an extra. With this being the case, you may have more luck changing the perspective from which you are viewing the issue; rather than trying to bolt on a gallery (where images are the focus), maybe you should trying creating a custom post type in WordPress and use the main body as the description and add the image path as a custom field. Doing it that way, you would have the option to theme gallery content differently than anything else and, as each gallery would behave like a post, you could use any related posts plugin to get what you’re after.