Create “painting” to go within a “gallery” (newbie question)

Hi,

I’m not sure if using Custom Post Types / Pods is even the right way to go about this, but I need to create a few image galleries of paintings, with each painting image in its gallery linking to its relevant page.

I have 4 galleries (Landscape, Portrait, etc), and a variety of painting images to go in each one.

I’ve tried to create a Custom Post Type of “Painting” and a Taxonomy of “Galleries”, with “Landscape” being one of the galleries, for example.

But I can’t seem to get them to work hierarchically. I need the URLs to be
/gallery/landscape/
and for the painting image page (the media attachment page, basically) to be:
/gallery/landscape/image-name-here

But all I can get to work is /gallery/image-name-here

What am I doing wrong?
Should both the Gallery and Painting each be a Custom Post Type?
Is using Custom Post Types even the right approach for this?

Thanks.