Differentiating post tags and categories for display

I am a WordPress newbie but I’ve managed to create a bespoke theme for a client. However, their requirements have changed and now they want to use tags, as well as categories, to aid topic collation. They want some of these ‘pages’ of collated tagged posts to appear in the main (top) navigation, but not all of them.

I’ve tried to read around the subject, but now I’m confused as to how best to proceed –

• do I bite the bullet and simply create a separate template ‘tag-123.php’ for each subject tag I want to segregate? This may result in many, many templates.
• do I use conditionals and, if so, how? What I’ve read on them has just confused me!
• do I use multiple loops?

Previously, I was just using categories. But the client started adding child categories and then wanting to collate child categories but omit the parent category! I’m hoping tags will let me get round this issue by allowing them to use a category as the primary ‘topic’ then use tags as the ‘secondary topic’.

As an example of what they want to achieve –
Post A has a category of ‘One’ and is tagged ‘Cheese’, ‘Banana’, ‘Bread’.
Post B has a category of ‘One’ and is tagged ‘Banana’, ‘Apple’.
Post C has a category of ‘Two’ and is tagged ‘Cheese’, ‘Apple’, Bread’.

All posts categorised with ‘One’ (Post A and Post B) can only be accessed via a link in the categories list, in the sidebar.

Post C (and any others categorised with ‘Two’) can be accessed via a link in the categories link, but also via a ‘page’ listed in the main menu.

In the main menu, they also want a ‘page’ titled ‘Cheese’, on which they want to display Post A and Post C (and any others tagged ‘Cheese’), but not Post B.

Access to other tagged posts, not collated onto ‘pages’ in the main menu, will be via tag cloud or similar widget.

I’ve been reading around this for hours now and I’m sure my brain is just over-complicating the issue! Any help would be very gratefully received.