Gilles, following is the code we used to achieve this, it changes title to the format '"StoreName" - "Category Name" - "Product Name"'. "ProductName" is only shown when someone navigates to product detail page.

File: Catalog.ascx.cs
Line: 161
Code Snippet:

                if (catalogNav.CategoryID != Null.NullInteger)
                {
                    Label ChngCtlgTitle = (Label)this.ContainerControl.FindControl("dnnTITLE").FindControl("lblTitle");
                    ChngCtlgTitle.Text = Localization.GetString("StoreName.Text", this.LocalResourceFile).ToString() + " - " + categoryInfo.CategoryName.ToString();
                    if (catalogNav.ProductID != Null.NullInteger)
                    {
                        ChngCtlgTitle.Text = ChngCtlgTitle.Text.ToString() + " - " + productInfo.ModelName.ToString();
                    }
                }

File: Catalog.ascx.resx
Action: Create another string named "StoreName.Text"
Value: <<Whatever Name you want>>

However, the only issue is that we have not given it a thought from "Child Portal" point of view.

Sincerely,