yeah.. I can see why they've gone that route with Trac - it doesn't have (or really need) a sidebar component, so they've not added one. For a site like yours I think this is a good way to go.. particularly a site that houses code snippets, diagrams etc. If all a sidebar is doing is containing a handful of links, at the expense of being able to scan full-width lines of code, I'd recommend keeping as much of your nav as possible up top (ie: sub-nav bnar under main nav, or drop menus etc).
Joomla - I've been working with 1.5 now for 2 months, after maintaining a couple of 1.0 sites - 1.5 is worth the upgrade in terms of the admin being *way* easier to understand (categories and sections easier to maintain). Themeing is pretty much the same though.
>> "We could start from scratch" - that'd be ideal, all else being equal.. but it's not, you've got a bunch of great content already seeded, and we're all short on time

so.. wrapping what you've already got into a cleaner package makes sense until you hit the Big Time (or it all get so frustrating that you have no choice - always a good motivator

Let me take a deeper look at the overall site and I'll email you off forum, probably - but hopefully there will be additional input on this thread.
As the original poster suggested - it's the "ease of use" that really needs a boost here. Shouldn't be too difficult to bust the site out of the frame.... that in itself will really help.