I had suspected that a database view we had was the culprit, but wasn't sure why it would be particularly slow, nor how to improve the speed.
But when I "dissolved" the view into separate tables inside the universe and let BO do the joining, things magically speeded up about 100 times.
Disadvantage: the view did some joining which I now have to do manually in BO -- specifically, in each report (not just once per universe).
But I think that's a fairly small price to pay for a great performance increase each time the report is run.
Now I just hope that this change didn't break anything else important (there's still a view involved, but one with only two tables, and one the tables was already present and I'm not sure how to link the view to the left half of the universe which uses one of those tables).